C++ Program to Implement Heap














































C++ Program to Implement Heap



DESCRIPTION:

The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as "heaps", regardless of how they may be implemented. In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority. 

A common implementation of a heap is the binary heap, in which the tree is a binary tree The heap data structure, specifically the binary heap, was introduced by J. W. J. Williams in 1964, as a data structure for the heapsort sorting algorithm. Heaps are also useful in several efficient graph algorithms such as Dijkstra's algorithm. When a heap is a complete binary tree, it has a smallest possible height a heap with N nodes and for each node a branches always has loga N height. 

OPERATIONS: 

The common operations involving heaps are: 

    Basic:

  • ->  find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively. 

  •      insert: adding a new key to the heap. 

  • -> extract-max (or extract-min): returns the node of maximum value from a max heap [or minimum value from a           min heap] after removing it from the heap. 

  • -> delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively 

  • -> replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance               once, not twice, and appropriate for fixed-size heaps. 

Creation: 

  • -> create-heap: create an empty heap. 

  • -> heapify: create a heap out of the given array of elements 

  • -> merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the           original heaps. 

  • -> meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original             heaps. 

     Inspection: 

  • -> size: return the number of items in the heap. 

  • -> is-empty: return true if the heap is empty, false otherwise. 

     Internal: 

  • -> increase-key or decrease-key: updating a key within a max- or min-heap, respectively 

  • -> delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap) 

  • -> sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift"       because node moves up the tree until it reaches the correct level, as in a sieve. 

  • -> sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or                 replacement. 

Heaps are basically of two types. 

  1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. 

  1. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of its children. The same property must be recursively true for all sub-trees in that Binary Tree. 

          

   The heap data structure has many applications. 

  • Heapsort: One of the best sorting methods being in-place and with no quadratic worst-case scenarios. 

  • Selection algorithms: A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap.[19] 

  • Graph algorithms: By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal-spanning-tree algorithm and Dijkstra's shortest-path algorithm. 

  • Priority Queue: A priority queue is an abstract concept like "a list" or "a map"; just as a list can be 

  •  implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods. 

  • K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream. Examples of the need for merging include external sorting and streaming results from distributed data such as a log structured merge tree. The inner loop is obtaining the min element, replacing with the next element for the corresponding input stream, then doing a sift-down heap operation. (Alternatively, the replace function.) (Using extract-max and insert functions of a priority queue are much less efficient.) 

  • Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array. 

 

SOURCE CODE:

/* C++ Program to Implement Heap */ #include <iostream> #include <cstdlib> #include <vector> #include <iterator> using namespace std; /* * Class Declaration */ class Heap { private: vector <int> heap; int left(int parent); int right(int parent); int parent(int child); void heapifyup(int index); void heapifydown(int index); public: Heap() {} void Insert(int element); void DeleteMin(); int ExtractMin(); void DisplayHeap(); int Size(); }; /* * Return Heap Size */ int Heap::Size() { return heap.size(); } /* * Insert Element into a Heap */ void Heap::Insert(int element) { heap.push_back(element); heapifyup(heap.size() -1); } /* * Delete Minimum Element */ void Heap::DeleteMin() { if (heap.size() == 0) { cout<<"Heap is Empty"<<endl; return; } heap[0] = heap.at(heap.size() - 1); heap.pop_back(); heapifydown(0); cout<<"Element Deleted"<<endl; } /* * Extract Minimum Element */ int Heap::ExtractMin() { if (heap.size() == 0) { return -1; } else return heap.front(); } /* * Display Heap */ void Heap::DisplayHeap() { vector <int>::iterator pos = heap.begin(); cout<<"Heap --> "; while (pos != heap.end()) { cout<<*pos<<" "; pos++; } cout<<endl; } /* * Return Left Child */ int Heap::left(int parent) { int l = 2 * parent + 1; if(l < heap.size()) return l; else return -1; } /* * Return Right Child */ int Heap::right(int parent) { int r = 2 * parent + 2; if(r < heap.size()) return r; else return -1; } /* * Return Parent */ int Heap::parent(int child) { int p = (child - 1)/2; if(child == 0) return -1; else return p; } /* * Heapify- Maintain Heap Structure bottom up */ void Heap::heapifyup(int in) { if (in >= 0 && parent(in) >= 0 && heap[parent(in)] > heap[in]) { int temp = heap[in]; heap[in] = heap[parent(in)]; heap[parent(in)] = temp; heapifyup(parent(in)); } } /* * Heapify- Maintain Heap Structure top down */ void Heap::heapifydown(int in) { int child = left(in); int child1 = right(in); if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) { child = child1; } if (child > 0) { int temp = heap[in]; heap[in] = heap[child]; heap[child] = temp; heapifydown(child); } } /* * Main Contains Menu */ int main() { Heap h; while (1) { cout<<"------------------"<<endl; cout<<"Operations on Heap"<<endl; cout<<"------------------"<<endl; cout<<"1.Insert Element"<<endl; cout<<"2.Delete Minimum Element"<<endl; cout<<"3.Extract Minimum Element"<<endl; cout<<"4.Print Heap"<<endl; cout<<"5.Exit"<<endl; int choice, element; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: cout<<"Enter the element to be inserted: "; cin>>element; h.Insert(element); break; case 2: h.DeleteMin(); break; case 3: cout<<"Minimum Element: "; if (h.ExtractMin() == -1) { cout<<"Heap is Empty"<<endl; } else cout<<"Minimum Element: "<<h.ExtractMin()<<endl; break; case 4: cout<<"Displaying elements of Hwap: "; h.DisplayHeap(); break; case 5: exit(1); default: cout<<"Enter Correct Choice"<<endl; } } return 0; }

More Articles of Manaswini Gade:

Name Views Likes
C++ Program to Implement Heap 3009 0

Comments