двоичная куча - как и когда использовать max-heapify - PullRequest
Новая
       40

двоичная куча - как и когда использовать max-heapify

1 голос
/ 21 января 2012

Я читаю о структуре данных кучи и не могу понять, когда использовать функцию max heapify и почему.

Я написал функцию вставки, которая всегда будет сохранять кучу как максимальную кучу, и я не вижу, когда будет использоваться максимальная куча.

Не могли бы вы объяснить? Спасибо

это мой код: 

    int  PARENT(int i)
    {
return i/2;
    }

    int LEFT(int i)
    {
return 2*i;
    }
    int RIGHT(int i )
   {
return 2*i +1;
   }


    void max_heapify(int *v, int index, int heapsize)
    {
int largest;
    int left = LEFT(index);
int right = RIGHT(index);
if (left<heapsize && v[left] > v[index])
    largest = left;
else 
    largest = index;
if (right < heapsize && v[right] > v[largest])
    largest = right;
if (largest !=index)
{
    v[index]  = v[index] ^v[largest];
    v[largest] = v[index] ^v[largest];
    v[index] = v[index] ^v[largest];
    max_heapify(v,largest,heapsize);
}

    }

    void insert(int *v, int * length, int value)
    {
v[++*length] = value;
int valuePos = *length;
int parent = PARENT(valuePos);
if (parent!=valuePos)
{
    while (v[parent] < v[valuePos])
    {
        v[parent] = v[parent] ^ v[valuePos];
        v[valuePos] = v[parent] ^v[valuePos];
        v[parent] = v[parent] ^ v[valuePos];
        valuePos = parent;
        parent = PARENT(valuePos);
    }
}

}

Ответы [ 4 ]

1 голос
/ 21 января 2012

Алгоритм heapify должен использоваться при превращении массива в кучу.Вы можете сделать это, вставив каждый элемент массива по очереди в новую кучу, но это займет время O ( n lg n ), в то время как heapify делает это в O ().n ) время.

0 голосов
/ 11 ноября 2015

Вам нужно вставить данные в кучу случайным образом, как в массиве.После этого вы можете вызвать функцию max heapify, чтобы сохранить свойство Max Heap.Вот мой код 

class max_heap{  
 private:               // are the private members of class
      int *arr;
      int size;
      int ind;
};

        void max_heap::bubbledown(int *ar, int i)
        {
         int len = ind - 1;
         int lt = 2 * i;
         int rt = lt + 1;
         while (lt <= len && rt <= len)                                         
         {
            if (arr[i] > arr[lt] && arr[i] > arr[rt])
                break;

            else if (ar[lt] > ar[rt])
            {
                if (ar[i] < ar[lt]){
                    swap(ar[i], ar[lt]);
                    i = lt;
                    lt = 2 * i;
                }
            }
            else if (ar[lt] < ar[rt])
            {
                if (ar[i] < ar[rt]){
                    swap(ar[i], ar[rt]);
                    i = rt;
                    rt = (2 * i)+1;
                }
            }
        }
    }

    void max_heap::heapify()
    {
        int len = ind - 1;
        for (int i = len; i >= 1 && (i/2) >= 1; i--)
        {
            if (arr[i] > arr[i/2])
            {
                swap(arr[i], arr[i/2]);
                bubbledown(arr, i);
            }
        }
    }
0 голосов
/ 21 января 2012

Функция max-heapify, как вы ее называете, является общей heapify функцией (куча может использовать любую допустимую функцию сравнения для сортировки своих элементов). Он предназначен для использования в качестве init функции для построения кучи из массива.

Сложности функций для работы с кучей (с их предполагаемым использованием):

  • init ( max-heapify ): O ( n ), используется для инициализации кучи из отсортированной последовательности (массива) (max- отсортировано, в вашем случае)
  • insert: O (lg n ), используется для вставки одного элемента в кучу (поддерживает дерево сортировки "отсортированным")
  • delete: O (lg n ), используется для удаления «наилучшего» (максимум, в вашем случае) элемента из кучи (поддерживает «сортировку» дерева кучи)

Но, поскольку этот вопрос помечен C++, вам также следует рассмотреть возможность использования std::set из STL вместо реализации своей собственной кучи. Сложности рассматриваемых операций такие же, как и для любой реализации кучи, и она может легко работать с любой функцией сравнения (предварительно написанной или написанной пользователем). Еще одним преимуществом реализации кучи является то, что это отсортированный контейнер, и вы можете легко выполнять итерации по всем элементам в отсортированном порядке (не только по первому), не разрушая структуру.

Единственная проблема с std::set заключается в том, что это уникальный контейнер, т. Е. В нем может существовать только 1 копия элемента с таким же ключом. Но есть решение и для этого - std::multiset сохраняет отсортированные экземпляры нескольких объектов с одним и тем же ключом.

Кроме того, в зависимости от требуемого использования (если с ключом поиска связано много данных), вы также можете попробовать std::map или std::multimap.

Если вы хотите создать свою собственную реализацию кучи, я настоятельно рекомендую поместить ее в отдельный класс (или даже в пространство имен), если вы намерены использовать C++ в полной мере. Если вы просто намереваетесь сохранить реализацию в том виде, в каком она есть, вам следует изменить метку вопроса на C

0 голосов
/ 21 января 2012
Ожидается, что

max_heapify вызовет обычный массив, чтобы сделать его кучей.И insert выполняет работу по обслуживанию, для которой массив (v в вашей функции) уже является кучей.

...