ADS

Heap Sort

Heap Sort  

A heap is a nearly complete binary tree with the following two properties:
  • Structural property: all levels are full, except possibly the last one, which is filled from left to right
  • Order (heap) property: for any node x, Parent(x) ≥ x
Heap Sort

Array Representation of Heaps

  • A heap can be stored as an array A.
  • Root of tree is A[1]
  • Left child of A[i] = A[2i]
  • Right child of A[i] = A[2i + 1]
  • Parent of A[i] = A[ i/2 ]
  • Heapsize[A] ≤ length[A]
The elements in the subarray A[(n/2+1) .. n] are leaves
Heap Sort

Max-heaps (largest element at root), have the max-heap property:  
  • for all nodes i, excluding the root:    
A[PARENT(i)] ≥ A[i]
Min-heaps (smallest element at root), have the min-heap property:
  • for all nodes i, excluding the root:  
A[PARENT(i)] ≤ A[i]


Adding/Deleting Nodes

New nodes are always inserted at the bottom level (left to right) and nodes are removed from the bottom level (right to left).
Heap Sort

Operations on Heaps

  • Maintain/Restore the max-heap property
    1. MAX-HEAPIFY
  • Create a max-heap from an unordered array
    1. BUILD-MAX-HEAP
  • Sort an array in place
    1. HEAPSORT
  • Priority queues


Heapify Property

Suppose a node is smaller than a child and Left and Right subtrees of i are max-heaps. To eliminate the violation:  
  • Exchange with larger child
  • Move down the tree
  • Continue until node is not smaller than children
Heap Sort


Algorithm

Max-Heapify(A, i, n)
{
l = Left(i)
r = Right(i)
largest=i;
if l ≤ n and A[l] > A[largest]
largest = l
if r ≤ n and A[r] > A[largest]
largest = r
if largest≠i  
exchange (A[i] , A[largest])             
Max-Heapify(A, largest, n)
}


Analysis:  

In the worst case Max-Heapify is called recursively h times, where h is height of the heap and since each call to the heapify takes constant time
Time complexity = O(h) = O(logn)


Building a Heap

Convert an array A[1 … n] into a max-heap (n = length[A]). The elements in the sub-array A[(n/2+1) .. n] are leaves. Apply MAX-HEAPIFY on elements between 1 and n/2⌋.
Heap Sort

Algorithm:  

Build-Max-Heap(A)
n = length[A]  
for i ← n/2 down to 1        
do MAX-HEAPIFY(A, i, n)


Time Complexity:

Running time:  Loop executes O(n) times and complexity of Heapify is O(lgn), therefore complexity of Build-Max-Heap is O(nlogn).
This is not an asymptotically tight upper bound
Heap Sort


Post a Comment

0 Comments