Heaps and Heapsort
1 October 2020 OSU CSE 1
• A heap is a binary tree of T that satisfies two properties:
Copyright By PowCoder代写 加微信 powcoder
– Global shape property: it is a complete binary tree
– Local ordering property: the label in each node is “smaller than or equal to” the label in each of its child nodes
1 October 2020 OSU CSE 2
• A heap is a binary tree of T that satisfies two properties:
– Global shape property: it is a complete
ry tree is one in which
all levels are “full” except possibly the
– Local ordering property: the label in each
bottom level, with any nodes on the
node is “smaller than or equal to” the label in bottom level as far left as possible.
each of its child nodes
1 October 2020 OSU CSE 3
• A heap is a binary tree of T that Also in the picture is (as with BSTs,
sorting, etc.) a total preorder that satisfies two properties:
makes this notion precise.
– Global shape property: it is a complete
binary tree
– Local ordering property: the label in each node is “smaller than or equal to” the label in each of its child nodes
1 October 2020 OSU CSE 4
Simplification
• For simplicity in the following illustrations, we use only one kind of example:
– T = integer – The ordering is ≤
• Because heaps are used in sorting, where duplicate values may be involved, we allow that multiple nodes in a heap may have the same labels (i.e., we will not assume that the labels are unique)
1 October 2020 OSU CSE 5
The Big Picture
1 October 2020 OSU CSE 6
The Big Picture
This tree’s root label y satisfies x≤y
1 October 2020
Observe: This tree is also
a heap; and for each node in this tree with label z, we have: x ≤ y ≤ z.
The Big Picture
1 October 2020
The Big Picture
This tree’s root label y satisfies x≤y
1 October 2020
The Big Picture
Observe: This tree is also
a heap; and for each node in this tree with label z, we have: x ≤ y ≤ z.
1 October 2020
Examples of Heaps
1 October 2020 OSU CSE 11
Non-Examples of Heaps
1 October 2020
Non-Examples of Heaps
Shape property is violated here: not all nodes at the bottom level are as far left as possible.
1 October 2020 OSU CSE
Non-Examples of Heaps
Ordering property is violated here: value is out of order with that of its right child.
1 October 2020
Non-Examples of Heaps
Shape property is violated: two levels are not “full”.
1 October 2020 OSU CSE
• A heap can be used to represent the
values in a SortingMachine, as follows:
– In changeToExtractionMode, arrange all
the values into a heap
– In removeFirst, remove the root, and adjust the slightly mutilated heap to make it a heap again
1 October 2020 OSU CSE 16
Why should this work? • A heap can be used to represent the
values in a SortingMachine, as follows:
– In changeToExtractionMode, arrange all
the values into a heap
– In removeFirst, remove the root, and adjust the slightly mutilated heap to make it a heap again
1 October 2020 OSU CSE 17
How removeFirst Can Work
• If the root is the only node in the heap, then after removing it, what remains is already a heap; nothing left to do
• If the root is not the only node, then removing it leaves an “opening” that must be filled by moving some other value in the heap into the opening
1 October 2020 OSU CSE 18
How removeFirst Can Work The question is:
• If the root is the only node in the
then after removing it, what remains is already a heap; nothing left to do
• If the root is not the only node, then removing it leaves an “opening” that must be filled by moving some other value in the heap into the opening
1 October 2020 OSU CSE 19
Example: A First Attempt
1 October 2020 OSU CSE 20
Example: A First Attempt
If we remove the root, leaving this opening …
1 October 2020
Example: A First Attempt
… we might move up the smaller child …
1 October 2020
Example: A First Attempt
… now creating another opening …
1 October 2020
Example: A First Attempt
… so, we might move up the smaller child.
1 October 2020
Example: A First Attempt
Is the result necessarily a heap?
1 October 2020
Example: A Second Attempt
1 October 2020 OSU CSE 26
Example: A Second Attempt
This time, let’s maintain the shape property …
1 October 2020
OSU CSE 27
Example: A Second Attempt
… by promoting the last node on the bottom level.
1 October 2020
Example: A Second Attempt
Now, we can “sift down” the root into its proper place …
1 October 2020
Example: A Second Attempt
… by swapping it with its smaller child …
1 October 2020
Example: A Second Attempt
… and then “sifting down” the root of that subtree.
1 October 2020
Example: A Second Attempt
Is the result necessarily a heap?
1 October 2020
Pseudo-Contract
* Restores a complete binary tree to be a heap * if only the root might be out of place.
* @updates t
* @requires
* [t is a complete binary tree] and
* [both subtrees of the root of t are heaps]
* @ensures
* [t is a heap with the same values as #t]
public static void siftDown (BinaryTree
1 October 2020 OSU CSE 33
Building a Heap In the First Place
• Suppose we have n values in a complete binary tree, but they are arranged without
regard to the heap ordering • How can we “heapify” it?
1 October 2020 OSU CSE 34
Pseudo-Contract
* Makes a complete binary tree into a heap. * @updates t
* @requires
* [t is a complete binary tree]
* @ensures
* [t is a heap with the same values as #t] */
public static void heapify (BinaryTree
1 October 2020 OSU CSE 35
• To see how you might implement
heapify, compare the contracts of siftDown and heapify
• The only difference: before we can call siftDown to make a heap, both subtrees
of the root must already be heaps
– Once they are heaps, just a call to siftDown will finish the job
1 October 2020 OSU CSE 36
How do we make the subtrees into heaps?
• To see how you might implement heapify, compare the contracts of
siftDown and heapify
• The only difference: before we can call
siftDown to make a heap, both subtrees of the root must already be heaps
– Once they are heaps, just a call to siftDown will finish the job
1 October 2020 OSU CSE 37
1 October 2020 OSU CSE 38
First, recursively “heapify” the left subtree.
1 October 2020 OSU CSE 39
Then, recursively “heapify” the right subtree.
1 October 2020
Then “sift down” the root, because now only the root might be out of place.
1 October 2020
Embedding a Heap in an array • While one could represent a heap using a
BinaryTree
not done this way
• Instead, a heap is usually represented
“compactly” using an array of T
1 October 2020 OSU CSE 42
Interpreting an array as a Heap
1 October 2020
Interpreting an array as a Heap
Because it’s a complete binary tree, the nodes
can be numbered top-to- bottom, left-to-right.
1 October 2020
1 October 2020
OSU CSE 45
At what index in the array is the left child of the node at index i?
1 October 2020
OSU CSE 46
At what index in the array is the right child of the node at index i?
1 October 2020
OSU CSE 47
Resources • Wikipedia:Heapsort
– http://en.wikipedia.org/wiki/Heapsort • Wikipedia:Heap(datastructure)
– http://en.wikipedia.org/wiki/Heap_(data_structure) • BigJava(4thed),Sections16.8,16.9
– https://library.ohio-state.edu/record=b8540788~S7
1 October 2020 OSU CSE 48
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com