Heapsort uses the same concept of heap. Sometimes we not only want to do a sorted array but we want to be able to insert and delete elements in the middle and may want to grab the maximum element at some point. A priority queue is an abstract data type from which we can grab a maximum value and be able to insert and delete values.
File: "pq1.cpp"
#include <iostream>using namespace std;int sizeG ;// To heapify a subtree rooted with node i which is// an index in arr[]. n is size of heapvoid heapify(int arr[], int n, int i1 ){ int largest = i1 ; // Initialize largest as root int l = 2 * i1 + 1; // left = 2*i + 1 int r = 2 * i1 + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i1) { swap(arr[i1], arr[largest]); // Recursively heapify the affected sub-tree heapify(arr, n, largest); }}// main function to do heap sortvoid heapSort(int arr[], int n){ // Build heap (rearrange array) for (int i1 = n / 2 - 1; i1 >= 0; i1--) heapify(arr, n, i1 ); // One by one extract an element from heap for (int i1 = n - 1; i1 > 0; i1--) { // Move current root to end swap(arr[0], arr[i1]); // call max heapify on the reduced heap heapify(arr, i1, 0); }}/* A utility function to print array of size n */void printArray(int arr[], int n){ for (int i1 = 0; i1 < n; ++i1) cout << arr[i1] << " "; cout << "\n";}void heapifyFromBottom(int arr[], int size, int index ){ int parentIndex = (index -1 ) / 2 ; while( parentIndex >= 0 && arr[parentIndex] < arr[index] ) { cout << parentIndex << " " << index << endl ; swap( arr[parentIndex] , arr[index] ); index = parentIndex ; parentIndex = (index -1 ) / 2 ; }}void insert ( int arr1[] , int size , int value ){ arr1[ size ] = value ; //printArray(arr1, 7 ); cout << "--" << endl ; size = size + 1 ; heapifyFromBottom( arr1, size, size-1 ) ;}void deleteNode ( int arr1[] , int size , int index ){ //arr1[ size++ ] = value ; arr1[ index ] = arr1[ --size ] ; printArray( arr1, size ); cout << "----" << endl ; int parentIndex = (index -1 ) / 2 ; if ( arr1[ index ] > arr1[ parentIndex ] ) heapifyFromBottom( arr1, size, index ) ; else heapify( arr1, size, index ) ;}// Driver codeint main(){ //int arr[] = { 9, 11, 13, 5, 6, 7, -1, -1 }; // int arr[] = { 9, 3, 13, 2, 1, 7, -1, -1 }; int arr[] = { 9, 12, 13, 10, 11, 7, -1, -1 }; //int n = sizeof(arr) / sizeof(arr[0]); int size = 6 ; //heapSort(arr, n); // Build heap (rearrange array) for (int i1 = size / 2 - 1; i1 >= 0; i1--) heapify(arr, size, i1 ); printArray(arr, size );// insert ( arr, size , 10 ) ; //20// size++ ;// printArray(arr, size ); // deleteNode( arr , size , 1 ) ; --size ; cout << "Sorted array is \n"; printArray(arr, size );}
Insertion
Insertion is easy as we add the node to the next rightmost position at
the lowest level and then call a function "heapifyFromBottom" . We keep moving the node up till we find the right place for it.