## Heap introduction

- Heap is a binary tree that stores priorities (or priority-element pairs) at the nodes.
- It has the following properties:
- All levels except last level are full. Last level is left filled.
- Priority of a node is atleast as large as that of its parent (min-heap) (or) vice-versa (max-heap).
- If the smallest element is in the root node, it results in a min-heap.
- If the largest element is in the root node, it results in a max-heap.
- A heap can be thought of as a priority queue. The most important node will always be at the root of the tree.
- Heaps can also be used to sort data, heap sort.
- The two most interesting operations in a heap is heapifyup and heapifydown.
- Heapifyup (assumption min-heap)
- Used to add a node to the heap. To add a node, it is inserted at the last empty space and heapifyup process is done.
- When a node is added, its key is compared to its parent. If parent key is smaller than the current node it is swapped. The process is repeated till the heap propery is met.
- Heapifydown
- Used during removal of a node. When a node is removed which is always the root (lowest in priority) the last available node in heap is replaced as the root and heapifydown process is done.
- The key of parent node is compared with the children. If any of the children have lower priority it is swapped with the parent. The process is repeated for the newly swapped node till the heap property is met.
- Good references.

## Demonstrates min-heap using arrays.

#include <iostream> #include <vector> #include <iterator> using namespace std; class Heap { public: Heap(); ~Heap(); void insert(int element); int deletemin(); void print(); int size() { return heap.size(); } private: int left(int parent); int right(int parent); int parent(int child); void heapifyup(int index); void heapifydown(int index); private: vector<int> heap; }; Heap::Heap() { } Heap::~Heap() { } void Heap::insert(int element) { heap.push_back(element); heapifyup(heap.size() - 1); } int Heap::deletemin() { int min = heap.front(); heap[0] = heap.at(heap.size() - 1); heap.pop_back(); heapifydown(0); return min; } void Heap::print() { vector<int>::iterator pos = heap.begin(); cout << "Heap = "; while ( pos != heap.end() ) { cout << *pos << " "; ++pos; } cout << endl; } void Heap::heapifyup(int index) { //cout << "index=" << index << endl; //cout << "parent(index)=" << parent(index) << endl; //cout << "heap[parent(index)]=" << heap[parent(index)] << endl; //cout << "heap[index]=" << heap[index] << endl; while ( ( index > 0 ) && ( parent(index) >= 0 ) && ( heap[parent(index)] > heap[index] ) ) { int tmp = heap[parent(index)]; heap[parent(index)] = heap[index]; heap[index] = tmp; index = parent(index); } } void Heap::heapifydown(int index) { //cout << "index=" << index << endl; //cout << "left(index)=" << left(index) << endl; //cout << "right(index)=" << right(index) << endl; int child = left(index); if ( ( child > 0 ) && ( right(index) > 0 ) && ( heap[child] > heap[right(index)] ) ) { child = right(index); } if ( child > 0 ) { int tmp = heap[index]; heap[index] = heap[child]; heap[child] = tmp; heapifydown(child); } } int Heap::left(int parent) { int i = ( parent << 1 ) + 1; // 2 * parent + 1 return ( i < heap.size() ) ? i : -1; } int Heap::right(int parent) { int i = ( parent << 1 ) + 2; // 2 * parent + 2 return ( i < heap.size() ) ? i : -1; } int Heap::parent(int child) { if (child != 0) { int i = (child - 1) >> 1; return i; } return -1; } int main() { // Create the heap Heap* myheap = new Heap(); myheap->insert(700); myheap->print(); myheap->insert(500); myheap->print(); myheap->insert(100); myheap->print(); myheap->insert(800); myheap->print(); myheap->insert(200); myheap->print(); myheap->insert(400); myheap->print(); myheap->insert(900); myheap->print(); myheap->insert(1000); myheap->print(); myheap->insert(300); myheap->print(); myheap->insert(600); myheap->print(); // Get priority element from the heap int heapSize = myheap->size(); for ( int i = 0; i < heapSize; i++ ) cout << "Get min element = " << myheap->deletemin() << endl; // Cleanup delete myheap; }OUTPUT:-

Heap = 700 Heap = 500 700 Heap = 100 700 500 Heap = 100 700 500 800 Heap = 100 200 500 800 700 Heap = 100 200 400 800 700 500 Heap = 100 200 400 800 700 500 900 Heap = 100 200 400 800 700 500 900 1000 Heap = 100 200 400 300 700 500 900 1000 800 Heap = 100 200 400 300 600 500 900 1000 800 700 Get min element = 100 Get min element = 200 Get min element = 300 Get min element = 400 Get min element = 500 Get min element = 600 Get min element = 700 Get min element = 800 Get min element = 900 Get min element = 1000

## 0 comments:

## Post a Comment