Рубрики

Медиана в потоке целых чисел (работающих целых чисел)

Heap, Математика

Учитывая, что целые числа читаются из потока данных. Найдите медиану элементов, прочитанную так, для эффективного способа. Для простоты предположим, что нет дубликатов. Например, рассмотрим поток 5, 15, 1, 3…

After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...

Чтобы было ясно, когда размер ввода нечетный, мы берем средний элемент отсортированных данных. Если входной размер четный, мы выбираем среднее из двух средних элементов в отсортированном потоке.

Обратите внимание, что результат — это эффективная медиана целых чисел, прочитанных из потока. Такой алгоритм называется онлайн-алгоритмом. Любой алгоритм, который может гарантировать вывод i -элементов после обработки i-го элемента, называется онлайн-алгоритмом . Давайте обсудим три решения вышеуказанной проблемы.

Метод 1: вставка сортировки

Если мы можем отсортировать данные так, как они появляются, мы можем легко найти медианный элемент. Insertion Sort — это один из таких онлайн-алгоритмов, который сортирует данные, появившиеся до сих пор. В любом случае сортировки, скажем, после сортировки i-го элемента, сортируются первые элементы i массива. Сортировка вставки не зависит от будущих данных, чтобы сортировать ввод данных до этой точки. Другими словами, сортировка вставкой учитывает данные, отсортированные до сих пор при вставке следующего элемента. Это ключевая часть сортировки вставок, которая делает его онлайн-алгоритмом.

Однако сортировка вставкой занимает O (n 2 ) время, чтобы отсортировать n элементов. Возможно, мы можем использовать бинарный поиск при вставке, чтобы найти местоположение следующего элемента за O (log n). Тем не менее, мы не можем сделать перемещение данных за O (log n). Независимо от того, насколько эффективна реализация, в случае сортировки вставкой требуется полиномиальное время.

Заинтересованный читатель может попробовать реализацию метода 1.

Метод 2: Дополненное самоуравновешенное дерево двоичного поиска (AVL, RB и т. Д.)

На каждом узле BST сохраняйте количество элементов в поддереве с корнем в этом узле. Мы можем использовать узел в качестве корня простого двоичного дерева, левый дочерний элемент которого самобалансирующийся BST с элементами, меньшими, чем root, а правый дочерний элемент самобалансирующего BST с элементами, большими, чем корень. Корневой элемент всегда содержит эффективную медиану .

Если левое и правое поддеревья содержат одинаковое количество элементов, корневой узел содержит среднее значение корневых данных левого и правого поддерева. В противном случае корень содержит те же данные, что и корень поддерева, в котором содержится больше элементов. После обработки входящего элемента левое и правое поддеревья (BST) отличаются максимально на 1.

Самостоятельная балансировка BST является дорогостоящей в управлении фактором балансировки BST. Однако они предоставляют отсортированные данные, которые нам не нужны. Нам нужна только медиана. Следующий метод использует кучи для отслеживания медианы.

Метод 3: Кучи

Подобно балансировке BST в методе 2 выше, мы можем использовать максимальную кучу с левой стороны, чтобы представить элементы, которые меньше эффективной медианы , и минимальную кучу с правой стороны, чтобы представить элементы, которые превышают эффективную медиану .

После обработки входящего элемента количество элементов в кучах максимально отличается на 1 элемент. Когда обе кучи содержат одинаковое количество элементов, мы выбираем среднее значение корневых данных кучи в качестве эффективной медианы . Когда кучи не сбалансированы, мы выбираем эффективную медиану из корня кучи, содержащей больше элементов.

Ниже приводится реализация вышеуказанного метода. Для алгоритма построения этих куч, пожалуйста, прочитайте выделенный код.

#include <iostream>

using namespace std;

  
// куча емкости
#define MAX_HEAP_SIZE (128)
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

  
//// Сервисные функции

  
// меняем а и б
inline

void Exch(int &a, int &b)

{

    int aux = a;

    a = b;

    b = aux;

}

  
// Большой и меньший используются в качестве компараторов

bool Greater(int a, int b)

{

    return a > b;

}

  

bool Smaller(int a, int b)

{

    return a < b;

}

  

int Average(int a, int b)

{

    return (a + b) / 2;

}

  
// функция Signum
// = 0, если a == b - куча сбалансирована
// = -1, если a <b - left содержит меньше элементов, чем right
// = 1, если a> b - left содержит больше элементов, чем right

int Signum(int a, int b)

{

    if( a == b )

        return 0;

  

    return a < b ? -1 : 1;

}

  
// Куча реализации
// Функциональность встроена в
// Куча абстрактного класса, чтобы избежать дублирования кода

class Heap

{

public:

    // Инициализирует массив кучи и требуется компаратор

    // в куче

    Heap(int *b, bool (*c)(int, int)) : A(b), comp(c)

    {

        heapSize = -1;

    }

  

    // Освобождает динамическую память

    virtual ~Heap()

    {

        if( A )

        {

            delete[] A;

        }

    }

  

    // Нам нужны только эти четыре интерфейса Heap ADT

    virtual bool Insert(int e) = 0;

    virtual int  GetTop() = 0;

    virtual int  ExtractTop() = 0;

    virtual int  GetCount() = 0;

  

protected:

  

    // Мы также используем местоположение 0 массива

    int left(int i)

    {

        return 2 * i + 1;

    }

  

    int right(int i)

    {

        return 2 * (i + 1);

    }

  

    int parent(int i)

    {

        if( i <= 0 )

        {

            return -1;

        }

  

        return (i - 1)/2;

    }

  

    // массив кучи

    int   *A;

    // Компаратор

    bool  (*comp)(int, int);

    // Размер кучи

    int   heapSize;

  

    // Возвращает верхний элемент структуры данных кучи

    int top(void)

    {

        int max = -1;

  

        if( heapSize >= 0 )

        {

            max = A[0];

        }

  

        return max;

    }

  

    // Возвращает количество элементов в куче

    int count()

    {

        return heapSize + 1;

    }

  

    // Heapification

    // Обратите внимание, что для текущей задачи отслеживания медианы

    // нам нужно кучи только к корню, всегда

    void heapify(int i)

    {

        int p = parent(i);

  

        // comp - различаем MaxHeap и MinHeap

        // просачивается вверх

        if( p >= 0 && comp(A[i], A[p]) )

        {

            Exch(A[i], A[p]);

            heapify(p);

        }

    }

  

    // Удаляет корень кучи

    int deleteTop()

    {

        int del = -1;

  

        if( heapSize > -1)

        {

            del = A[0];

  

            Exch(A[0], A[heapSize]);

            heapSize--;

            heapify(parent(heapSize+1));

        }

  

        return del;

    }

  

    // Помощник для вставки ключа в кучу

    bool insertHelper(int key)

    {

        bool ret = false;

  

        if( heapSize < MAX_HEAP_SIZE )

        {

            ret = true;

            heapSize++;

            A[heapSize] = key;

            heapify(heapSize);

        }

  

        return ret;

    }

};

  
// Спецификация кучи для определения MaxHeap

class MaxHeap : public Heap

{

private:

  

public:

    MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater)  {  }

  

    ~MaxHeap()  { }

  

    // Обёртка для возврата корня Max Heap

    int GetTop()

    {

        return top();

    }

  

    // Обертка для удаления и возврата корня Max Heap

    int ExtractTop()

    {

        return deleteTop();

    }

  

    // Обертка для возврата # элементов Max Heap

    int  GetCount()

    {

        return count();

    }

  

    // Обертка для вставки в Max Heap

    bool Insert(int key)

    {

        return insertHelper(key);

    }

};

  
// Специализация кучи для определения MinHeap

class MinHeap : public Heap

{

private:

  

public:

  

    MinHeap() : Heap(new int[MAX_HEAP_SIZE], &Smaller) { }

  

    ~MinHeap() { }

  

    // Обёртка для возврата корня Min Heap

    int GetTop()

    {

        return top();

    }

  

    // Обертка для удаления и возврата корня Min Heap

    int ExtractTop()

    {

        return deleteTop();

    }

  

    // Обёртка для возврата # элементов Min Heap

    int  GetCount()

    {

        return count();

    }

  

    // Обертка для вставки в Min Heap

    bool Insert(int key)

    {

        return insertHelper(key);

    }

};

  
// Функция, реализующая алгоритм для поиска медианы.

int getMedian(int e, int &m, Heap &l, Heap &r)

{

    // Сбалансированы ли кучи? Если да, sig будет 0

    int sig = Signum(l.GetCount(), r.GetCount());

    switch(sig)

    {

    case 1: // В левой (max) куче больше элементов

  

        if( e < m ) // текущий элемент помещается в левую (максимальную) кучу

        {

            // Удалить верхний элемент из левой кучи и

            // вставить в правую кучу

            r.Insert(l.ExtractTop());

  

            // текущий элемент помещается в левую (максимальную) кучу

            l.Insert(e);

        }

        else

        {

            // текущий элемент помещается в правую (минимальную) кучу

            r.Insert(e);

        }

  

        // обе кучи сбалансированы

        m = Average(l.GetTop(), r.GetTop());

  

        break;

  

    case 0: // Левая и правая куча содержат одинаковое количество элементов

  

        if( e < m ) // текущий элемент помещается в левую (максимальную) кучу

        {

            l.Insert(e);

            m = l.GetTop();

        }

        else

        {

            // текущий элемент помещается в правую (минимальную) кучу

            r.Insert(e);

            m = r.GetTop();

        }

  

        break;

  

    case -1: // В правой (мин) куче больше элементов

  

        if( e < m ) // текущий элемент помещается в левую (максимальную) кучу

        {

            l.Insert(e);

        }

        else

        {

            // Удалить верхний элемент из правой кучи и

            // вставить в левую кучу

            l.Insert(r.ExtractTop());

  

            // текущий элемент помещается в правую (минимальную) кучу

            r.Insert(e);

        }

  

        // обе кучи сбалансированы

        m = Average(l.GetTop(), r.GetTop());

  

        break;

    }

  

    // Нет необходимости возвращать, м уже обновлено

    return m;

}

  

void printMedian(int A[], int size)

{

    int m = 0; // эффективная медиана

    Heap *left  = new MaxHeap();

    Heap *right = new MinHeap();

  

    for(int i = 0; i < size; i++)

    {

        m = getMedian(A[i], m, *left, *right);

  

        cout << m << endl;

    }

  

    // C ++ более гибок, не допускает утечек

    delete left;

    delete right;

}
// Код драйвера

int main()

{

    int A[] = {5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4};

    int size = ARRAY_SIZE(A);

  

    // Вместо A мы также можем использовать данные, прочитанные из потока

    printMedian(A, size);

  

    return 0;

}

Сложность времени: если мы опускаем способ чтения потока, сложность медианного поиска равна O (N log N) , так как нам нужно прочитать поток, и из-за вставки / удаления кучи.

На первый взгляд приведенный выше код может показаться сложным. Если вы внимательно читаете код, это простой алгоритм.

Медиана потока бегущих целых чисел с использованием STL

— Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Медиана в потоке целых чисел (работающих целых чисел)

0.00 (0%) 0 votes