CmSc 250 Intro to Algorithms

Sorting Algorithms
Heapsort

Animation

Learning Goals
Exam-like questions

  1. Heapsort

    2.

    Based on Priority Queues
    Sorts in O(NlogN) time by performing N times deleteMin operations.

    Why O(NlogN)?

      • Each deleteMin operation takes logN running time.
      • N times performing deleteMin → NlogN running time

    Basic algorithm (not very efficient - extra memory required):

    1. Store N elements in a binary heap tree.
    2. Perform deleteMin operation N times, storing each element deleted from
      the heap into another array.
    3. Copy back the array.

    Improvements: Use the same array to store the deleted elements
    instead of using another array

    How can we do this?

    After each deletion we percolate down the hole that is formed after the deletion,
    and as a result we get a vacant position in the array - the last cell.
    There we store the deleted element.

    When all the elements are deleted and stored in the same array following the above method,
    the elements will be there in reversed order.

    What is the remedy for this?

    Store the elements in the binary heap tree in reverse order of priority -
    then at the end the elements in the array will be in correct order.

    Complexity of heap sort: O(NlogN) is the rough estimate.

    Here is an example of heapsort.

Learning Goals

  • Be able to explain how heapsort works and its complexity.

Exam-like questions

  1. Explain the complexity of heapsort
  2. Given an array e.g. 17, 23, 10, 1, 7, 16, 9, 20, sort it on paper using heapsort
    Write down explicitly each step.
Back to Contents page
Created by Lydia Sinapova