Двоичная куча : разновидность полного бинарного дерева

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

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

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

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

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

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

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

log₂ (N+1)↑,

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

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

log₂ (10+1)↑ = 3,46↑ = 4

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

N·log₂N.

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

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

Реализация класса кучи

1
2
3
4
5
6
7
8
9
10
11
12

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);  // упорядочение кучи
};

Конструктор кучи

1
2
3
4

Heap :: Heap() {
h = new int[SIZE];
HeapSize = 0;
}

Добавление элемента кучи

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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++;
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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;
  }
}

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

1
2
3
4
5
6

void Heap:: out(void) {
  for(int i=0; i< HeapSize; i++) {
    cout << h[i] << " "; }
  cout << endl;
}

Упорядочение кучи

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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 максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.

Удаление вершины кучи (максимального элемента)

1
2
3
4
5
6
7
8

int Heap:: getmax(void) {
  int x;
  x = h[0];
  h[0] = h[HeapSize-1];
  HeapSize—;
  heapify(0);
  return(x);
}

Пример

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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;
}

Результат выполнения