Analysis of Algorithms Heap Sort

Analysis of Algorithms Heap Sort

•The (binary) heap data structure is an array object that is nearly complete binary tree

•Each node of the tree corresponds to an element of the array that stores the value in the node.

•The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point.

•An array A that represents a heap is an object with two attributes:

–length[A], which is the number of elements in the array,

–heap-size[A], the number of elements in the heap stored within array A.

•Given the index of a node, its parent and children can be calculated as

•PARENT(i)

  return ⌊i/2⌋

•LEFT(i)

  return 2i

•RIGHT(i)

  return 2i + 1

•the height of a node in a heap to be the number of edges on the longest simple downward path from the node to a leaf

•The height of the heap to be the height of its root.

•Since a heap of n elements is based on a complete binary tree, its height is Θ(lg n)

Max-Heap Property: For all nodes i, excluding the root. A[Parent(i)] ≥ A[i].

Min-Heap Property: For all nodes i, excluding the root. A[Parent(i)] ≤ A[i].

Example: Max-Heap

 Maintaining the Heap Property

MAX-HEAPIFY(A, i)

   l ← LEFT(i)

   r ← RIGHT(i)

   if l ≤ heap-size[A] and A[l] > A[i]

     then largest ← l

   else largest ← i

   if r ≤ heap-size[A] and A[r] > A[largest]

  then largest ← r

    if largest ≠ i

     then    exchange A[i] ↔ A[largest]

      MAX-HEAPIFY(A, largest)

The way MAX-HEAPIFY works:

•   Compare A[i] , LEFT[i] and RIGHT[i].

•   If necessary, swap A[i] with the larger of the two children to preserve heap property.

•   Continue this process of comparing and swapping down the heap, until subtree rooted at i is max-heap. If we hit a leaf, then the subtree rooted at the leaf is trivially a max-heap.

Run MAX-HEAPIFY on the following heap example

MAX-HEAPIFY

Analysis

Time

O(lg n).

Analysis

Heap is almost-complete binary tree, hence must process O(lg n) levels, with constant work at each level (comparing 3 items and maybe swapping 2).

-Another time is o(h)

-This time is for a node of height ‘h’

Building a Heap

The following procedure, given an unordered array, will produce a max-heap.

BUILD-MAX-HEAP(A)

Heap-size[A] ß length[A]

for i ß Floor(length[A]/2) downto 1

  do MAX-HEAPIFY(A,i)