Beginner's Guide

# Standard Library Heap OperationsHeap OperationsHeap Ops

## BackgroundBackground

### What Are Heaps?General

• a family of data structures (not to be confused with the memory partition for dynamic storage)
• they contain objects (keys) that can be ordered
• they are referred to as "max-heap" or "min-heap" depending on the ordering
• they are usually used to implement priority queues
• get maximum usually in O(1) (constant time)
• remove maximum usually in O(log N) (logarithmic time)
• insert new key usually in O(1) or O(log N)
• increase/decrease key change value of a key, usually in O(1) or O(log N)

The Heap Data Structure

### Binary Max HeapsBinary Max

• keys are stored in nodes of a binary tree
• keys must be orderable, i.e., comparable
• heap property: all children of a parent with key P must contain keys than are smaller or equal to P ⇒ root has maximum
• get maximum: O(1) (constant time)
• remove maximum: O(log N) (logarithmic time)
• insert: O(log N)
• increase key: O(log N)

### Representing Binary Trees With ArraysRepresenting Binary TreesArray Rep.

• The tree must either consist of a single node or it must be complete on all inner levels.
• The rightmost leafs might be missing.

## Heap ManipulationManipulate

### Heaps In The C++ Standard LibraryC++ Standard Library HeapsStd.Lib.Heaps

• make_heap: reorder a sequence of keys into a binary heap
• push_heap: insert a new key
• pop_heap: remove maximum

If all you want is a priority queue, use the dedicated standard container type std::priority_queue.

### Initialize HeapInit

std::vector<int> h {1,6,4,2,9,7,8};
// make max heap (default)
make_heap(begin(h), end(h));
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 7 4
// make min heap
make_heap(begin(h), end(h), std::greater<>{});
for (int x : h) { cout << x << ' '; }  // 1 2 4 9 6 7 8

std::vector<int> h {1,6,4,2,9,7,8};
// make max heap (default)
std::ranges::make_heap(h);
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 7 4
// make min heap
std::ranges::make_heap(h, std::greater<>{});
for (int x : h) { cout << x << ' '; }  // 1 2 4 9 6 7 8

### Shrink HeapShrink

std::vector<int> h {1,2,4,9,8,7,6};
make_heap(begin(h), end(h));  // 9 6 8 2 1 4 7
// remove element from heap:
pop_heap(begin(h), end(h));
auto oldmax = h.back();  // oldmax = 9
h.pop_back();
for (int x : h) { cout << x << ' '; }  // 8 6 7 2 1 4

std::vector<int> h {1,2,4,9,8,7,6};
std::ranges::make_heap(h);  // 9 6 8 2 1 4 7
// remove element from heap:
std::ranges::pop_heap(h);
auto oldmax = h.back();  // oldmax = 9
h.pop_back();
for (int x : h) { cout << x << ' '; }  // 8 6 7 2 1 4

### Grow HeapGrow

std::vector<int> h {1,2,4,8,6,7};
make_heap(begin(h), end(h));  // 8 6 7 2 1 4
// add new element to heap:
h.push_back(9);
push_heap(begin(h), end(h));
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 4 7

std::vector<int> h {1,2,4,8,6,7};
std::ranges::make_heap(h);  // 8 6 7 2 1 4
// add new element to heap:
h.push_back(9);
std::ranges::push_heap(h);
for (int x : h) { cout << x << ' '; }  // 9 6 8 2 1 4 7

## Auxiliary OperationsAuxiliary OpsAuxiliary Ops

### sort_heap (Heap → Sorted Array)sort_heap

// max heap:
std::vector<int> h {9,6,8,2,1,7,4};
// make sorted vector:
sort_heap(begin(h), end(h));
for (int x : h) { cout << x << ' '; }  // 1 2 4 6 7 8 9

// max heap:
std::vector<int> h {9,6,8,2,1,7,4};
// make sorted vector:
std::ranges::sort_heap(h);
for (int x : h) { cout << x << ' '; }  // 1 2 4 6 7 8 9

### is_heapis_heapC++11

// max heap:
std::vector<int> h {9,7,8,6,2,1,4};
cout << is_heap(begin(h), end(h));  // true
// not a max heap:
std::vector<int> v {1,2,3,4,5};
cout << is_heap(begin(v), end(v));  // false

// max heap:
std::vector<int> h {9,7,8,6,2,1,4};
cout << std::ranges::is_heap(h);  // true
// not a max heap:
std::vector<int> v {1,2,3,4,5};
cout << std::ranges::is_heap(v);  // false

### is_heap_untilis_heap_untilC++11

std::vector<int> h {9,7,8,6,8,1,4};
auto e = is_heap_until(begin(h), end(h));
if (e == end(h)) {
cout << "complete heap!\n";
} else {
cout << *e;  // 8
auto const idx = distance(begin(h), e);  // 4
cout << "heap until index " << idx;
// add one more element to heap
push_heap(begin(h), next(e));

}

std::vector<int> h {9,7,8,6,8,1,4};
auto e = std::ranges::is_heap_until(h);
if (e == end(h)) {
cout << "complete heap!\n";
} else {
cout << *e;  // 8
auto const idx = distance(begin(h), e);  // 4
cout << "heap until index " << idx;
// erase non-heap part
h.erase(e, end(h));

}