PPT On Heapsort

Download

 Heapsort Presentation Transcript:
1.Design and Analysis of Algorithms

2.Sorting Revisited
So far we’ve talked about two algorithms to sort an array of numbers
What is the advantage of merge sort?
What is the advantage of insertion sort?
Next on the agenda: Heapsort
Combines advantages of both previous algorithms
Worst case O(n lg n) – like merge sort.
Sorts in place – like insertion sort.

3.Heaps
A heap can be seen as a complete binary tree:

4.A heap can be seen as a complete binary tree:
The book calls them “nearly complete” binary trees; can think of unfilled slots as null pointers

5.In practice, heaps are usually implemented as arrays:

6.Heap data structure
To represent a complete binary tree as an array:
The root node is A[1]
Node i is A[i]
The parent of node i is A[i/2] (note: integer divide)
The left child of node i is A[2i]
The right child of node i is A[2i + 1]

7.Referencing Heap Elements

8.The Heap Property
Heaps also satisfy the heap property: (for max-heaps)
    A[Parent(i)] ? A[i]        for all nodes i > 1
In other words, the value of a node is at most the value of its parent
Where is the largest element in a heap stored?
Definitions:
The height of a node in the tree = the number of edges on the longest downward path from node to a leaf
The height of a tree/heap = ???

9.Heap Height
What is the height of an n-element heap? Why?

10.Heap Operations: Max-Heapify()
Max-Heapify(): maintain the heap property
Given: a node i in the heap with children l and r
Given: two subtrees rooted at l and r, assumed to be heaps
Problem: The subtree rooted at i may violate the heap property (How?)
Action: let the value of the parent node “float down” so subtree at i satisfies the heap property

11.Heap Operations: Max-Heapify()
Max-Heapify(A, i, n)
    l = Left(i);  r = Right(i);
    if (l <= n and A[l] > A[i])
        then largest = l
    else
        largest = i
    if (r <= n and A[r] > A[largest])
        then largest = r
    if (largest ? i)
        then Swap(A[ i], A[largest])
                Max-Heapify(A, largest,n)


12.Max-Heapify() Example

13.Heap sort Trace

14.Heapify