Двійкова купа являє собою повне бінарне дерево, для якого виконується основне властивість купи: пріоритет кожної вершини більше пріоритетів її нащадків.
У найпростішому випадку пріоритет кожної вершини можна вважати рівним її значенням. В такому випадку структура називається max-купа. оскільки корінь поддерева є максимумом з значень елементів поддерева.
В якості альтернативи, якщо порівняння перевернути, то найменший елемент буде завжди кореневим вузлом, такі купи називають min-купами.
Двійкову купу зручно зберігати у вигляді одновимірного масиву, причому
- лівий нащадок вершини з індексом i має індекс 2 * i + 1,
- правий нащадок вершини з індексом i має індекс 2 * i + 2.
Корінь дерева (купи) - елемент з індексом 0.
Висота двійковій купи дорівнює висоті дерева, тобто
де N - кількість елементів масиву, ↑ - округлення в більшу сторону до найближчого цілого.
Для представленої купи
Спосіб побудувати купу з невпорядкованого масиву - це по черзі додати всі його елементи. Тимчасова оцінка такого алгоритму оцінюється як
Можна побудувати купу за N кроків. Для цього спочатку слід побудувати дерево з усіх елементів масиву, не піклуючись про дотримання основного властивості купи, а потім викликати метод упорядкування для всіх вершин, у яких є хоча б один нащадок (так як піддерева, що складаються з однієї вершини без нащадків, вже впорядковані) .
Нащадки гарантовано є у перших heapSize / 2 вершин, де heapSize - розмір купи.
Реалізація класу купи
static const int SIZE = 100; // максимальний розмір купи
int * h; // покажчик на масив купи
int HeapSize; // розмір купи
public:
Heap (); // конструктор купи
void addelem (int); // додавання елемента купи
void outHeap (); // вивід елементів купи в формі купи
void out (); // вивід елементів купи в формі масиву
int getmax (); // видалення вершини (максимального елемента)
void heapify (int); // впорядкування купи
>;