17
Removing the Top of a Heap
❶Move the last node onto
the root.
23
45
42
18
Removing the Top of a Heap
❶Move the last node onto
the root.
23
27
42
19
Removing the Top of a Heap
❶Move the last node onto
the root.
❷Push the out-of-place
23
27
42
20
Should I continue with the reheapification downward?
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. 19
4222135
23
42
27
21
Removing the Top of a Heap
❶Move the last node onto
the root.
❷Push the out-of-place
23
42
35
22
Reheapification downward can stop under two circumstances:
Removing the Top of a Heap
✔The children all have
keys <= the out-of-place
node, or
23
42
35
23
Implementing a Heap
❐We will store the
data from the
nodes in a
An array of data
23
42
35
24
Implementing a Heap
❐Data from the root
goes in the
first
23
42
35
25
Implementing a Heap
❐Data from the next
row goes in the
23
42
35
26
Implementing a Heap
❐Data from the next
row goes in the
23
42
35
27
Implementing a Heap
❐Data from the next
row goes in the
23
42
35
28
Important Points about the
Implementation
❐The links between the tree’s
nodes are not actually stored as
pointers, or in any other way.
23
42
35
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
23
42
35
30
❐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
Summary
31
Feel free to send your ideas to:
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force