Меню

Двоичная куча

Структуры данных / Двоичная куча

 

Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков.

В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча, поскольку корень поддерева является максимумом из значений элементов поддерева.

В качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами.

Двоичную кучу удобно хранить в виде одномерного массива, причем

  • левый потомок вершины с индексом i имеет индекс 2*i+1,
  • правый потомок вершины с индексом i имеет индекс 2*i+2.

Двоичная куча

Корень дерева (кучи) – элемент с индексом 0.

Высота двоичной кучи равна высоте дерева, то есть

log2 (N+1)↑,

где N – количество элементов массива, ↑ – округление в большую сторону до ближайшего целого.

Для представленной кучи

log2 (10+1)↑ = 3,46↑ = 4

Способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма оценивается как

N·log2N.

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

Потомки гарантированно есть у первых heapSize/2 вершин, где heapSize – размер кучи.

Реализация класса кучи
class Heap {
  static const int SIZE = 100; // максимальный размер кучи
  int *h;         // указатель на массив кучи
  int HeapSize; // размер кучи
public:
  Heap();  // конструктор кучи
  void addelem(int);  // добавление элемента кучи
  void outHeap();  // вывод элементов кучи в форме кучи
  void out();  // вывод элементов кучи в форме массива
  int getmax();  // удаление вершины (максимального элемента)
  void heapify(int);  // упорядочение кучи
};
Конструктор кучи
Heap :: Heap() {
  h = new int[SIZE];
  HeapSize = 0;
}
Добавление элемента кучи

Новый элемент добавляется на последнее место в массиве, то есть позицию с максимальным индексом.
Добавление элемента кучи

Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае новый элемент «поднимается» на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи.
Формирование кучи
Просеивание элемента кучи

Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна log2 N.

void Heap :: addelem(int n) {
  int i, parent;
  i = HeapSize;
  h[i] = n;
  parent = (i-1)/2;
  while(parent >= 0 && i > 0)  {
    if(h[i] > h[parent]) {
      int temp = h[i];
      h[i] = h[parent];
      h[parent] = temp;
    }
    i = parent;
    parent = (i-1)/2;
  }
  HeapSize++;
}
Вывод элементов кучи

Вывод элементов в форме кучи

void Heap:: outHeap(void) {
  int i = 0;
  int k = 1;
  while(i < HeapSize) {
    while((i < k) && (i < HeapSize)) {
      cout << h[i] << » «;
      i++;
    }
    cout << endl;
    k = k * 2 + 1;
  }
}

Вывод элементов кучи в форме массива

void Heap:: out(void) {
  for(int i=0; i< HeapSize; i++) {
    cout << h[i] << » «; }
  cout << endl;
}
Упорядочение кучи
void Heap:: heapify(int i) {
  int left, right;
  int temp;
  left = 2*i+1;
  right = 2*i+2;
  if(left < HeapSize) {
    if(h[i] < h[left]) {
      temp = h[i];
      h[i] = h[left];
      h[left] = temp;
      heapify(left);
    }
  }
  if(right < HeapSize) {
    if(h[i] < h[right]) {
      temp = h[i];
      h[i] = h[right];
      h[right] = temp;
      heapify(right);
    }
  }
}

В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.

Удаление вершины кучи (максимального элемента)
int Heap:: getmax(void) {
  int x;
  x = h[0];
  h[0] = h[HeapSize-1];
  HeapSize—;
  heapify(0);
  return(x);
}

Пример Создать бинарную кучу из 16 элементов. Определить максимальный элемент.

int main() {
  Heap heap;
  int k;
  system(«chcp 1251»);
  system(«cls»);
  for(int i=0; i<16; i++) {
    cout << «Введите элемент « << i+1 << «: «;
    cin >> k;
    heap.addelem(k);
  }
  heap.outHeap();
  cout  << endl;
  heap.out();
  cout  << endl << «Максимальный элемент: « << heap.getmax();
  cout  << endl << «Новая куча:» << endl;
  heap.outHeap();
  cout  << endl;
  heap.out();
  cout  << endl << «Максимальный элемент: « << heap.getmax();
  cout  << endl << «Новая куча:» << endl;
  heap.outHeap();
  cout  << endl;
  heap.out();
  cin.get();cin.get();
  return 0;
}

Результат выполнения
Результат выполнения: Двоичная куча
Назад


Назад: Структуры данных

Комментариев к записи: 8

  • Петр
    Пожалуйста, докажите, что потомки i-го элемента будут иметь номера 2i+1 и 2i+2
    Ответить ↓
    • Елена Вставская
      Для нулевого элемента потомки имеют номера 2*0+1=1 и 2*0+2=2. Для элемента 1 потомки имеют номера 2*1+1=3 и 2*1+2=4. Так для каждого.
      Ответить ↓
    • Елена Вставская
      Володя, теоретически да, но на это нужно время. Можешь помочь, не возражаю)
      Ответить ↓
      • Владимир
        А материал надо на C++ делать? А то у меня сейчас есть для языка Java.
        Ответить ↓
        • Елена Вставская
          На этом сайте только C++. Другие языки только в комментариях изредка встречаются.
          Ответить ↓

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Пальто-одеяло

Пальто-одеяло

Рубрики

Свежие записи

Социальные сети

Группа Вконтакте

Все права защищены ©

Яндекс.Метрика