1	Heaps Chapter 10 has several programming projects, including a project that uses heaps. This presentation shows you what a heap is, and demonstrates two of the important heap algorithms.
2	Heaps A heap is a certain kind of complete binary tree.
3	Heaps A heap is a certain kind of complete binary tree.
4	Heaps Complete binary tree.
5	Heaps Complete binary tree.
6	Heaps Complete binary tree.
7	Heaps Complete binary tree.
8	Heaps Complete binary tree.
9	Heaps Complete binary tree.
10	Heaps Complete binary tree.
11	Heaps A heap is a certain kind of complete binary tree.
12	Heaps A heap is a certain kind of complete binary tree.
13	Adding a Node to a Heap Put the new node in the next available spot. Push the new node upward, swapping with its parent until the new node reaches an acceptable location.
14	Adding a Node to a Heap Put the new node in the next available spot. Push the new node upward, swapping with its parent until the new node reaches an acceptable location.
15	Adding a Node to a Heap Put the new node in the next available spot. Push the new node upward, swapping with its parent until the new node reaches an acceptable location.
16	Adding a Node to a Heap The parent has a key that is >= new node, or The node reaches the root. The process of pushing the new node upward is called reheapification upward.
17	Removing the Top of a Heap Move the last node onto the root.
18	Removing the Top of a Heap Move the last node onto the root.
19	Removing the Top of a Heap Move the last node onto the root. Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.
20	Removing the Top of a Heap Move the last node onto the root. Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.
21	Removing the Top of a Heap Move the last node onto the root. Push the out-of-place node downward, swapping with its larger child until the new node reaches an acceptable location.
22	Removing the Top of a Heap The children all have keys <= the out-of-place node, or The node reaches the leaf. The process of pushing the new node downward is called reheapification downward.
23	Implementing a Heap We will store the data from the nodes in a partially-filled array.
24	Implementing a Heap Data from the root goes in the first location of the array.
25	Implementing a Heap Data from the next row goes in the next two array locations.
26	Implementing a Heap Data from the next row goes in the next two array locations.
27	Implementing a Heap Data from the next row goes in the next two array locations.
28	Important Points about the Implementation The links between the tree's nodes are not actually stored as pointers, or in any other way. The only way we "know" that "the array is a tree" is from the way we manipulate the data.
29	Important Points about the Implementation If you know the index of a node, then it is easy to figure out the indexes of that node's parent and children. Formulas are given in the book.
30	Summary A heap is a complete binary tree, where the entry at each node is greater than or equal to the entries in its children. To add an entry to a heap, place the new entry at the next available spot, and perform a reheapification upward. To remove the biggest entry, move the last node onto the root, and perform a reheapification downward.
31	THE END