#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::swap;
void Heapify(vector<int>& arr, int n, int i){
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// If left child is larger than root
if(left < n && arr[left] > arr[largest]) largest = left;
// If right child is larger than largest so far
if(right < n && arr[right] > arr[largest]) largest = right;
// If largest is not root
if(largest != i){
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
Heapify(arr, n, largest);
}
}
void HeapSort(vector<int>& arr){
int n = arr.size();
// build max heap
// The parent of the ith element is at index i / 2 - 1.
// Therefore, the parent of the nth element is at index n / 2 - 1
for(int i = n / 2 - 1; i >= 0; i--) Heapify(arr, n, i);
// One by one extract an element from heap
for(int i = n - 1; i > 0; i--){
// Move current root to end
swap(arr[0], arr[i]);
// Call max heapify on the reduced heap (re-build max heap)
Heapify(arr, i, 0);
}
}
void PrintArray(const vector<int>& arr){
for(int i : arr)
cout << i << " ";
cout << "\n";
}
int main(){
vector<int> arr = {4, 6, 8, 5, 9};
cout << "Original Array:\n";
PrintArray(arr);
HeapSort(arr);
cout << "Sorted Array:\n";
PrintArray(arr);
return 0;
}
A max-heap viewed as (a) a binary tree and (b) an arry. The root of the tree is A[1], and given the index i of a node, there’s a simple way to compute the indices of it’s parent, left child, and right child with the one-line procedures PARENT, LEFT, and RIGHT:
PARENT(i): $$\left \lfloor i / 2 \right \rfloor$$
LEFT(i): $$\left \lfloor 2i \right \rfloor$$
RIGHT(i): $$\left \lfloor 2i + 1 \right \rfloor$$
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satify a heap property, the specifics of which depend on the kind of heap. In max-heap, the max-heap property is that for every node i other than the root
A[PARENT(i)] >= A[i]
that is, the value of a node is at most the value of its parent. Thus, the largest value in a max-heap is stored at the root, the subtree rooted at a node contains values no larger than that contained at the node itself. A min-heap is organized in the opposite way: the min-heap property is that for every node i other than the root,
A[PARENT(i)] <= A[i]
MAX-HEAPIFY:
The action of MAX-HEAPIFY(A, 2), where, A.heap-size = 10.
BUILD-MAX-HEAP
The operation of BUILD-MAX-HEAP, showing the data structure before the call to MAX-HEAPIFY in line 3 of BUILD-MAX-HEAP.