Overview

Another unique kind of tree, called a heap, can be used for implementing solutions to several different problems, including the priority queue ADT and a special sorting algorithm, heapsort. Today we’ll focus on this data structure and what is is used for.

Basic Learning Objectives

Before class, you should be able to:

  • Define what the priority queue ADT is
  • Define what complete means for binary trees
  • Explain how a heap maintains its nodes
  • Explain the idea behind heapsort

Advanced Learning Objectives

After class, you should be able to:

  • Implement a heap
  • Use a heap to perform heapsort

Reading

You should read/watch the following: