# CS代写 CSE 11 – cscodehelp代写

Heaps and Heapsort
1 October 2020 OSU CSE 1

• A heap is a binary tree of T that satisfies two properties:

Copyright By cscodehelp代写 加微信 cscodehelp

– 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.
* @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 t) {…}
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 t) {…}
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 (as suggested in the pseudo-contracts above), it is generally
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