Standard Library Heap Operations Heap Operations Heap Ops
New to C++'s standard library algorithms? ⇒ Short Introduction
- 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
Supported operations typically include
- 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
HeapData Structure
- 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
Time complexity of operations
- get maximum: O(1) (constant time)
- remove maximum: O(log N) (logarithmic time)
- insert: O(log N)
- increase key: O(log N)
Almost full binary trees can be represented by arrays
- The tree must either consist of a single node or it must be complete on all inner levels.
- The rightmost leafs might be missing.
Heaps In The C++ Standard Library C++ Standard Library Heaps Std.Lib.Heaps
- binary max heaps
- represented by an array-like container
- maximum = tree root = first element in array
- keys must be orderable (default: using
operator <)
Heap operations = algorithms that reorder elements in an (iterator) range
make_heap: reorder a sequence of keys into a binary heappush_heap: insert a new keypop_heap: remove maximum- …
If all you want is a priority queue, use the dedicated standard
container type std::priority_queue.
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
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) { std::cout << x << ' '; } // 9 6 8 2 1 7 4
std::cout << '\n';
// make min heap
make_heap(begin(h), end(h), std::greater<>{});
for (int x : h) { std::cout << x << ' '; } // 1 2 4 9 6 7 8
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
std::vector<int> h {1,6,4,2,9,7,8};
// make max heap (default)
std::ranges::make_heap(h);
for (int x : h) { std::cout << x << ' '; } // 9 6 8 2 1 7 4
std::cout << '\n';
// make min heap
std::ranges::make_heap(h, std::greater<>{});
for (int x : h) { std::cout << x << ' '; } // 1 2 4 9 6 7 8
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
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
std::cout << "oldmax: " << oldmax << '\n';
h.pop_back();
for (int x : h) { std::cout << x << ' '; } // 8 6 7 2 1 4
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
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
std::cout << "oldmax: " << oldmax << '\n';
h.pop_back();
for (int x : h) { std::cout << x << ' '; } // 8 6 7 2 1 4
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
std::vector<int> h {1,2,4,8,6,7};
make_heap(begin(h), end(h)); // 8 6 7 2 1 4
for (int x : h) { std::cout << x << ' '; }
std::cout << '\n';
// add new element to heap:
h.push_back(9);
push_heap(begin(h), end(h));
for (int x : h) { std::cout << x << ' '; } // 9 6 8 2 1 4 7
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
std::vector<int> h {1,2,4,8,6,7};
std::ranges::make_heap(h); // 8 6 7 2 1 4
for (int x : h) { std::cout << x << ' '; }
std::cout << '\n';
// add new element to heap:
h.push_back(9);
std::ranges::push_heap(h);
for (int x : h) { std::cout << x << ' '; } // 9 6 8 2 1 4 7
std::cout << '\n';
}
Auxiliary Operations Auxiliary Ops Auxiliary Ops
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
// 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) { std::cout << x << ' '; } // 1 2 4 6 7 8 9
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
// 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) { std::cout << x << ' '; } // 1 2 4 6 7 8 9
std::cout << '\n';
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
// max heap:
std::vector<int> h {9,7,8,6,2,1,4};
std::cout << is_heap(begin(h), end(h)) << '\n'; // true
// not a max heap:
std::vector<int> v {1,2,3,4,5};
std::cout << is_heap(begin(v), end(v)) << '\n'; // false
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
// max heap:
std::vector<int> h {9,7,8,6,2,1,4};
std::cout << std::ranges::is_heap(h) << '\n'; // true
// not a max heap:
std::vector<int> v {1,2,3,4,5};
std::cout << std::ranges::is_heap(v) << '\n'; // false
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
std::vector<int> h {9,7,8,6,8,1,4};
auto e = is_heap_until(begin(h), end(h));
if (e == end(h)) {
std::cout << "complete heap!\n";
} else {
std::cout << *e << '\n'; // 8
auto const idx = distance(begin(h), e); // 4
std::cout << "heap until index " << idx << '\n';
// add one more element to heap
push_heap(begin(h), next(e));
…
}
}
#include <vector>
#include <iostream>
#include <algorithm>
int main () {
std::vector<int> h {9,7,8,6,8,1,4};
auto e = std::ranges::is_heap_until(h);
if (e == end(h)) {
std::cout << "complete heap!\n";
} else {
std::cout << *e << '\n'; // 8
auto const idx = distance(begin(h), e); // 4
std::cout << "heap until index " << idx << '\n';
// erase non-heap part
h.erase(e, end(h));
…
}
}
Comments…