Heap Sort

Heaps can be used in sorting an array. In max-heaps, maximum element will always be at the root. Heap Sort uses this property of heap to sort the array.

Consider an array Arr which is to be sorted using Heap Sort.

• Initially build a max heap of elements in Arr.
• The root element, that is Arr[1], will contain maximum element of Arr. After that, swap this element with the last element of Arr and heapify the max heap excluding the last element which is already in its correct position and then decrease the length of heap by one.
• Repeat the step 2, until all the elements are in their correct position.

Implementation:

    void heap_sort(int Arr[ ])

    {
        int heap_size = N;

        build_maxheap(Arr);
        for(int i = N; i >= 2 ; i-- )
        {
            swap|(Arr[ 1 ], Arr[ i ]);
            heap_size = heap_size - 1;
            max_heapify(Arr, 1, heap_size);
        }
    }
 

Complexity:
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(NlogN).

Example:
In the diagram below,initially there is an unsorted array Arr having 6 elements and then max-heap will be built.

After building max-heap, the elements in the array Arr will be:

Step 1: 8 is swapped with 5.
Step 2: 8 is disconnected from heap as 8 is in correct position now and.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected.

After all the steps, we will get a sorted array.

Contributed by: Akash SharmaDid you find this tutorial helpful? Yes  NoTEST YOUR UNDERSTANDINGHeaps

You are given a list of amount of money of T people, one by one. After each element in the list print the top 3 richest people’s amount of money.

Input:
First line contains an integer, T, number of queries.
Next T lines contains an integer each, X.
ith query contains amount of money ith person have.

Output:
For each query, print the top 3 richest people’s amount of money in the town and if there are less than 3 people in town then print -1.

Constraints:
1≤T≤105
1≤X≤106

SAMPLE INPUT 

5
1
2
3
4
5

SAMPLE OUTPUT 

-1
-1
3 2 1
4 3 2
5 4 3