Building a Heap - Example

Building a Heap - Example

Building a max-heap from the following unsorted array results in the first heap example. i starts off as 5.

MAX-HEAPIFY  is applied to subtrees rooted at nodes (in order): 16, 2, 3, 1, 4.

Analysis

•Simple bound:

•O(n) calls to MAX-HEAPIFY

•Each of which takes O(lg n)

•time = O(n lg n)

HEAP-SORT(A)

BUILD-MAX-HEAP(A)

for i ß length [A] downto 2

  do exchange A[1] with A[i]

        heap-size[A] ß heap-size[A] – 1

        MAX-HEAPIFY(A,1) 

HEAP-SORT - Analysis

BUILD -MAX-HEAP: O(n)

for loop: n – 1 times

exchange elements: O(1)

MAX-HEAPIFY: O(lg n)

Total time: O(n lg n).

Though heapsort is a great algorithm, a well-implemented quicksort usually beats it in practice.