Overview
A max heap is a specialized data structure that represents a complete binary tree where the value of each node is greater than or equal to the values of its children. In other words, in a max heap, the parent nodes always have larger values compared to their child nodes.
The key property of a max heap is that the maximum element in the heap is always stored at the root node. This allows for efficient retrieval of the maximum element in constant time, regardless of the size of the heap.
Heap Algorithms operate on various types of containers such as sequence, associative and unordered to organize the elements of a range that allows for fast retrieval of the element with the highest value at any moment (with pop_heap), even repeatedly, while allowing for fast insertion of new elements (with push_heap).
Graphical Visualization of the heaps can be seen from this link.
Heap Algorithm functions accepts parameters like
- iterators such as random access
- predicates such as binary
The parameter type Compare is a function that accepts two inputs and returns bool value (true or false).
For example, bool isless(int i, int j) {return i < j;} or [](int i, int j) {return i < j;}
Details
| Name | Description |
|---|---|
| Rearranges the elements in the range [first,last] in such a way that they form a heap. The elements are compared using operator< for the first version, and comp for the second. |
//1 vector<int> v{2,4,1,6,3,7,5}; /* 7 / \ / \ 6 5 / \ / \ / \ / \ 4 3 1 2 */ //v:[{7} {6,5} {4, 3, 1, 2}] make_heap (begin(v), end(v)); //2 v.assign({2,4,1,6,3,7,5}); /* 1 / \ / \ 3 2 / \ / \ / \ / \ 6 4 7 5 */ //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); | |
| Sorts the elements in the heap range [first,last] as per the comparison function. The elements are compared using operator< for the first version, and comp for the second. Note that the comparison function should be same as the function used to construct the heap. The range loses its properties as a heap. |
Example //1 vector<int> v{2,4,1,6,3,7,5}; //v:[{7} {6,5} {4, 3, 1, 2}] make_heap (begin(v), end(v)); //v:{1,2,3,4,5,6,7} sort_heap (begin(v), end(v)); //2 v.assign({2,4,1,6,3,7,5}); //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); //v:{7,6,5,4,3,2,1} sort_heap (begin(v), end(v), greater<int>()); | |
| Returns true if the range [first,last] forms a heap, as if constructed with make_heap. The elements are compared using operator< for the first version, and comp for the second. |
Example cout << boolalpha; //1 vector<int> v{1,2,3,4,5,6,7}; //prints false cout << is_heap (begin(v), end(v)) << endl; //2 //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); //prints true cout << is_heap (begin(v), end(v),greater<int>()) << endl; | |
| Test if value exists in sorted sequence. Returns true if any element in the range [first,last] is equivalent to val, and false otherwise. The elements are compared using operator< for the first version, and comp for the second. |
Example //1 vector<int> v{2,4,1,6,3,7,5}; //v:[{7} {6,5} {4, 3, 1, 2}] make_heap (begin(v), end(v)); //v:{7,6,5,4,3,1,2,8} v.push_back(8); //itr:begin(v)+7 auto itr = is_heap_until (begin(v), end(v)); //v:{7,6,5,4,3,1,2,4} v.back()=4; //itr:end(v) itr = is_heap_until (begin(v), end(v)); //2 v.assign({2,4,1,6,3,7,5}); //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); //v:{1,3,2,6,4,7,5,0} v.push_back(0); //itr:begin(v)+7 itr = is_heap_until (begin(v), end(v), greater<int>()); //v:{1,3,2,6,4,7,5,8} v.back()=8; //itr:end(v) itr = is_heap_until (begin(v), end(v), greater<int>()); | |
| Push element into heap range. Given a heap in the range [first,last-1], this function extends the range considered a heap to [first,last] by placing the value in (last-1) into its corresponding location within it. A range can be organized into a heap by calling make_heap. After that, its heap properties are preserved if elements are added and removed from it using push_heap and pop_heap, respectively. The elements are compared using operator< for the first version, and comp for the second. |
Example vector<int> v{2,4,1,6,3,7,5}; //v:[{7} {6,5} {4, 3, 1, 2}] make_heap (begin(v), end(v)); //v:{7,6,5,4,3,1,2,8} v.push_back(8); //v:[{8} {7,5} {6, 3, 1, 2} {4}] push_heap(begin(v), end(v)); //2 v.assign({2,4,1,6,3,7,5}); //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); //v:{1,3,2,6,4,7,5,8} v.push_back(8); //v:[{1} {3,2} {6, 4, 7, 5} {8}] push_heap(begin(v), end(v), greater<int>()); | |
| Sorts the elements in the heap range [first,last] into ascending order. The elements are compared using operator< for the first version, and comp for the second. Note that the comparison function should be same as the function used to construct the heap.The range loses its properties as a heap. |
Example vector<int> v{2,4,1,6,3,7,5}; //v:[{7} {6,5} {4, 3, 1, 2}] make_heap (begin(v), end(v)); //v:[{6} {4,5} {2, 3, 1} 7] pop_heap(begin(v), end(v)); //prints 7 cout << v.back() << endl; //2 v.assign({2,4,1,6,3,7,5}); //v:[{1} {3,2} {6, 4, 7, 5}] make_heap (begin(v), end(v), greater<int>()); //v:[{2} {3,5} {6, 4, 7} 1] pop_heap(begin(v), end(v), greater<int>()); //prints 1 cout << v.back() << endl; | |
The example depicts the usage.
No comments:
Post a Comment