Heap sort
Heap sort is one of the best and efficient sorting methods in computer programming and was invented by J. W. J. Williams in 1964. Heap sort involves building a Heap data structure from the given array and then utilizing the Heap to sort the array. To understand this, let’s find out what is a Heap.
Heap is a special tree-based data structure, that satisfies special heap properties, like –
Shape Property – Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled.
Heap Property – All nodes are either greater than or less than or equal to each of its children. Greater parent nodes heap is called a Max-Heap and small parent nodes heap is called Min-Heap.
How heap sort works?
Heap sort algorithm is divided into two basic parts –
-
A heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree.
-
Once heap is built, the first element of the Heap is either largest or smallest, so put the first element of the heap in an array.
-
The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch is simple expressions. [Example – For a zero-based array, the root node is stored at index 0; if i is the index of the current node, then parent(i) = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer. leftChild(i) = 2*i + 1, rightChild(i) = 2*i + 2]
-
Then a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array.
-
Again make heap using the remaining elements, to pick again the first element of the heap and put it into the array.
-
Keep on doing the same repeatedly until you have the complete sorted list in your array.
-
The heap is updated after each removal to maintain the heap property.
-
Once all objects have been removed from the heap, the result is a sorted array.
Logic of Heap Sort
# heapify
for i = n/2:1, sink(a,i,n)
invariant: a[1,n] in heap order
# sortdown
for i = 1:n,
swap a[1,n-i+1]
sink(a,1,n-i)
invariant: a[n-i+1,n] in final position
end
# sink from i in a[1..n]
function sink(a,i,n):
# {lc,rc,mc} = {left,right,max} child index
lc = 2*i
if lc > n, return # no children
rc = lc + 1
mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
if a[i] >= a[mc], return # heap ordered
swap a[i,mc]
sink(a,mc,n)
return result
Performance
-
Worst Case Time Complexity: O(n log n)
-
Best Case Time Complexity: O(n)
-
Average Time Complexity: O(n log n)
-
Space Complexity: O(1)
No comments:
Post a Comment