In a Heap, a unique type of tree-based data structure, in which the tree is a complete binary tree.
Heap Data Structure Operations
Heapify: A technique for making a heap out of an array.
Insertion: The process of inserting an element into an existing heap with time complexity O.
Deletion: The process of deleting the top element of the heap or the element with the highest priority, then organizing the heap and returning the element with time complexity O.
Peek: To inspect or locate the heap's most recent constituent (max or min element for max and min heap).
Types of Heap Data Structure
Normally, there can be two types of Heaps:
Max-Heap: In a Max-Heap, the key at the root node must be greater than the keys at all of its descendants. The same property must be true for all subtrees in that Binary Tree.
Min-Heap: In a Min-Heap, the key at the root node must be the smallest of all the keys at its descendants. The same property must be true for all subtrees in that Binary Tree.
Min Heap and Max Heap Implementation in C++
Max Heap construction algorithm
Add a new node to the end of the heap.
Give the node a new value.
Compare this child node's value to that of its parent.
If the value of parent is less than the value of child, switch them.
Steps 3 and 4 should be repeated until Heap property holds.
Syntax
#include <iostream> #include <vector> #include <algorithm> #include <stdexcept> usingnamespacestd; // Data structure to store a max-heap node structPriorityQueue { private: // vector to store heap elements vector<int> A; // return parent of `A[i]` // don't call this function if `i` is already a root node intPARENT(int i) { return (i - 1) / 2; } // return left child of `A[i]` intLEFT(int i) { return (2*i + 1); } // return right child of `A[i]` intRIGHT(int i) { return (2*i + 2); } // Recursive heapify-down algorithm. // The node at index `i` and its two direct children // violates the heap property voidheapify_down(int i) { // get left and right child of node at index `i` int left = LEFT(i); int right = RIGHT(i); int largest = i; // compare `A[i]` with its left and right child // and find the largest value if (left < size() && A[left] > A[i]) { largest = left; } if (right < size() && A[right] > A[largest]) { largest = right; } // swap with a child having greater value and // call heapify-down on the child if (largest != i) { swap(A[i], A[largest]); heapify_down(largest); } } // Recursive heapify-up algorithm voidheapify_up(int i) { // check if the node at index `i` and its parent violate the heap property if (i && A[PARENT(i)] < A[i]) { // swap the two if heap property is violated swap(A[i], A[PARENT(i)]); // call heapify-up on the parent heapify_up(PARENT(i)); } } public: // return size of the heap unsignedintsize() { return A.size(); } // Function to check if the heap is empty or not boolempty() { return size() == 0; } // insert key into the heap voidpush(int key) { // insert a new element at the end of the vector A.push_back(key); // get element index and call heapify-up procedure int index = size() - 1; heapify_up(index); } // Function to remove an element with the highest priority (present at the root) voidpop() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw out_of_range("Vector<X>::at() : " "index is out of range(Heap underflow)"); } // replace the root of the heap with the last element // of the vector A[0] = A.back(); A.pop_back(); // call heapify-down on the root node heapify_down(0); } // catch and print the exception catch (const out_of_range &oor) { cout << endl << oor.what(); } } // Function to return an element with the highest priority (present at the root) inttop() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw out_of_range("Vector<X>::at() : " "index is out of range(Heap underflow)"); } // otherwise, return the top (first) element return A.at(0); // or return A[0]; } // catch and print the exception catch (const out_of_range &oor) { cout << endl << oor.what(); } } }; // Max Heap implementation in C++ intmain() { PriorityQueue pq; // Note: The element's value decides priority pq.push(3); pq.push(2); pq.push(15); cout << "Size is " << pq.size() << endl; cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); pq.push(5); pq.push(4); pq.push(45); cout << endl << "Size is " << pq.size() << endl; cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << endl << boolalpha << pq.empty(); pq.top(); // top operation on an empty heap pq.pop(); // pop operation on an empty heap return0; }
In the Min Heap construction algorithm, we expect the child node's value to be less than the parent node's value.
Syntax:
#include <iostream> #include <vector> #include <algorithm> #include <stdexcept> usingnamespacestd; // Data structure to store a min-heap node structPriorityQueue { private: // vector to store heap elements vector<int> A; // return parent of `A[i]` // don't call this function if `i` is already a root node intPARENT(int i) { return (i - 1) / 2; } // return left child of `A[i]` intLEFT(int i) { return (2*i + 1); } // return right child of `A[i]` intRIGHT(int i) { return (2*i + 2); } // Recursive heapify-down algorithm. // The node at index `i` and its two direct children // violates the heap property voidheapify_down(int i) { // get left and right child of node at index `i` int left = LEFT(i); int right = RIGHT(i); int smallest = i; // compare `A[i]` with its left and right child // and find the smallest value if (left < size() && A[left] < A[i]) { smallest = left; } if (right < size() && A[right] < A[smallest]) { smallest = right; } // swap with a child having lesser value and // call heapify-down on the child if (smallest != i) { swap(A[i], A[smallest]); heapify_down(smallest); } } // Recursive heapify-up algorithm voidheapify_up(int i) { // check if the node at index `i` and its parent violate the heap property if (i && A[PARENT(i)] > A[i]) { // swap the two if heap property is violated swap(A[i], A[PARENT(i)]); // call heapify-up on the parent heapify_up(PARENT(i)); } } public: // return size of the heap unsignedintsize() { return A.size(); } // Function to check if the heap is empty or not boolempty() { return size() == 0; } // insert key into the heap voidpush(int key) { // insert a new element at the end of the vector A.push_back(key); // get element index and call heapify-up procedure int index = size() - 1; heapify_up(index); } // Function to remove an element with the lowest priority (present at the root) voidpop() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw out_of_range("Vector<X>::at() : " "index is out of range(Heap underflow)"); } // replace the root of the heap with the last element // of the vector A[0] = A.back(); A.pop_back(); // call heapify-down on the root node heapify_down(0); } // catch and print the exception catch (const out_of_range &oor) { cout << endl << oor.what(); } } // Function to return an element with the lowest priority (present at the root) inttop() { try { // if the heap has no elements, throw an exception if (size() == 0) { throw out_of_range("Vector<X>::at() : " "index is out of range(Heap underflow)"); } // otherwise, return the top (first) element return A.at(0); // or return A[0]; } // catch and print the exception catch (const out_of_range &oor) { cout << endl << oor.what(); } } }; // Min Heap implementation in C++ intmain() { PriorityQueue pq; // Note: The element's value decides priority pq.push(3); pq.push(2); pq.push(15); cout << "Size is " << pq.size() << endl; cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); pq.push(5); pq.push(4); pq.push(45); cout << endl << "Size is " << pq.size() << endl; cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << pq.top() << " "; pq.pop(); cout << endl << boolalpha << pq.empty(); pq.top(); // top operation on an empty heap pq.pop(); // pop operation on an empty heap return0; }
