Heap

Heap: A heap is a partially ordered tree, typically a binary tree. Heaps use the index starting typically from ‘i’.
When represented as an array, the parent element can be found at i/2, left child at 2*i, right child at 2 *i+1, where ‘i’ is the index of the location.
A ‘N’ element heap contains leaves starting from arr[N/2+1] to arr[N].
The ‘heapify()’ method is used to reorder the tree at each index to make a tree/array satisfy the max or min heap conditions.

Pseudo Code

Max_Heapify(int[] arr, int i, int n){
 int left = 2i, right = 2*i+1, large = i;
 if(left < n && arr[left] > arr[i])
  large = left;
 if(right < n && arr[right] > arr[large])
  large = right;
 if(i!=large)
  swap(arr[i],arr[large]);
Max_Heapify(arr, large, n);
}

Build Max Heap

An array can be used to build max heap by repeatedly using the heapify() method in all the non child nodes(N/2 to 0). The amortized performance is O(n) though it’s like n/2 * logn.

Pseudo Code

for(int i=n/2;i>0;i–){
max_heapify(arr, i, n);
}

Heap Sort
We can sort an array of elements using the below method:
1) Build a max heap
2) Swap the max element which is usually at the start of the array with the last element.
3) Apply heapify method on the array excluding the last element.
4) Repeat the steps 2-3 until we get the sorted array.

Complexity: As we know max_heapify has complexity O(logN), build_maxheap has complexity O(N) and we run max_heapify N-1 times in heap_sort function, therefore complexity of heap_sort function is O(N logN).

Priority Queues
A priority queue is a normal queue with constant time access to the min or max elements. This is done by heapifying the queue elements after each insert or delete. This allows the head of the queue is always the min or max element depending on the priority queue implementation.

Methods
Typically a max priority queue has the following methods, each of these take O(log n) time.
returnMax() – returns the front element of the queue.
extractMax() or delete() – you read the max element at the front and do a delete, that is swap with the last element and repeteadly call heapify method.
insertVal() – You insert a new value at the end and check for any heap violation property.
increaseVal() – Basically an update operation. once you update a certain node value, you go up the path until root to make sure the newly added value doesn’t value the heap property. if it does, you swap values along the way.