Heapsort

Before jumping into Heap sort, we have to have the understanding of the below

• Binary Tree
• Full Binary Tree
• Complete Binary Tree
• Heap – Heap is a complete binary tree
• Max Heap / Min Heap

Heap sort

We have two different approach in heap sort

• Create Heap & Delete the root element
• Heapify & Delete the root element

Create heap time complexity will be O(n logn)
Heapify time complexity will be O(n)

Insert a new element in a max/min heap is O(1) to O(logn)
Deletion of a new element in a max/min heap is O(logn)

public void doHeapSort(int a[]) {
        int unsortedArrayLength = a.length;
        for(int i=0;i<a.length;i++) {
            for(int h=unsortedArrayLength;h>0;h--) {
                heapify(a, h, unsortedArrayLength);
            }
            swap(a, 0, unsortedArrayLength-1);
            unsortedArrayLength--;
        }
    }

    public void heapify(int a[], int indexToHeapify, int arrayLength) {
        int maxChildPosition;
        if(2*indexToHeapify <= arrayLength) {
            if((2*indexToHeapify)+1 <= arrayLength) {
                //Node is full BT. Have 2 children
                if(a[2*indexToHeapify] > a[(2*indexToHeapify)-1]) {
                    maxChildPosition = (2*indexToHeapify)+1;
                } else {
                    maxChildPosition = (2*indexToHeapify);
                }
            } else {
                //Node is Complete BT. Have only one child
                maxChildPosition = (2*indexToHeapify);
            }
            if(a[maxChildPosition-1] > a[indexToHeapify-1]) {
                swap(a, indexToHeapify-1, maxChildPosition-1);
                heapify(a, maxChildPosition, arrayLength);
            }
        }
    }

    private void swap(int[] array, int firstPosition, int secondPosition) {
        int temp = array[firstPosition];
        array[firstPosition] = array[secondPosition];
        array[secondPosition] = temp;
    }

Priority Queue

Priority Queue will not follow FIFO. Elements will be taken out by their priority value.