CS代写 CSE 15 - PowCoder代写

More About Heaps
5 September 2020 OSU CSE 1

Complete Binary Tree As Array

• To use an array to represent a complete binary tree, you need more information:
– An int index of the root of the tree of interest
• There might be many subtrees inside the tree rooted
at index 0, and you might want to do something to these subtrees as well as to the whole tree
– An int index of the last node of the whole tree • You need to know which entries in the array contain
tree node labels; entries at index 0 through the last index are useful, but others are “junk”
5 September 2020 OSU CSE 2

5 September 2020

Note that the array might
be larger than the tree
now, even if at one point
they were the same size.
How could this happen?
5 September 2020 OSU CSE 4

For the gray tree:
top = 0 last = 4
5 September 2020

For the pink
top = 1 last = 4
5 September 2020 OSU CSE 6

For the blue tree:
top = 2 last = 4
5 September 2020 OSU CSE 7

Note that all the entries in a
10 are in positions top through
given subtree (e.g., blue here)
last of the array—but not all entries of the array in that
range are in the subtree!
5 September 2020 OSU CSE 8

SortingMachine5a Representation
private Comparator machineOrder; private boolean insertionMode; private Queue entries;
private T[] heap;
private int heapSize;
5 September 2020 OSU CSE 9

SortingMachine5a Representation
private Comparator machineOrder; private boolean insertionMode; private Queue entries;
private T[] heap;
private int heapSize;
This instance variable is set by the constructor, and does not change; it determines the ordering of T values.
5 September 2020

SortingMachine5a Representation
private Comparator machineOrder; private boolean insertionMode; private Queue entries;
private T[] heap;
private int heapSize; 5 September 2020 OSU CSE
This instance variable records whether this is
in insertion mode.

SortingMachine5a Representation
private Comparator machineOrder; private boolean insertionMode; private Queue entries;
private T[] heap;
private int heapSize;
This instance variable is 0 while this is in
insertion mode; it holds the number of entries of this while it is in
extraction mode.
5 September 2020

SortingMachine5a Correspondence
* @correspondence
* if $this.insertionMode then
* this = (true, $this.machineOrder,
multiset_entries($this.entries))
this = (false, $this.machineOrder, multiset_entries(
5 September 2020
$this.heap[0, $this.heapSize)))
OSU CSE 15

SortingMachine5a Convention
* @convention
* if $this.insertionMode then * $this.heapSize = 0
* $this.entries = < > and
for all i: integer
where (0 <= i and i < |$this.heap|) ([entry at position i in $this.heap is not null]) and SUBTREE_IS_HEAP($this.heap, 0, $this.heapSize – 1, [relation computed by $this.machineOrder.compare method]) and 0 <= $this.heapSize <= |$this.heap| 5 September 2020 OSU CSE 16 * * * * * * * * */ SortingMachine5a Convention * @convention * if $this.insertionMode then * $this.heapSize = 0 * $this.entries = < > and
This mathematical definition (not shown on slides) means what you should think it does.
* * * * * * * * */
for all i: integer
where (0 <= i and i < |$this.heap|) ([entry at position i in $this.heap is not null]) and SUBTREE_IS_HEAP($this.heap, 0, $this.heapSize – 1, [relation computed by $this.machineOrder.compare method]) and 0 <= $this.heapSize <= |$this.heap| 5 September 2020 OSU CSE 17 Commutative Diagram (≤, true, <3, 1>, ?, 0)
5 September 2020 OSU CSE 18

Commutative Diagram
Does this concrete value satisfy the representation invariant?
(≤, true, <3, 1>, ?, 0)
5 September 2020 OSU CSE 19

Commutative Diagram
What abstract value does it represent?
(≤, true, <3, 1>, ?, 0) 5 September 2020 OSU CSE

Commutative Diagram
What does the contract say the abstract result of this method call will be?
(≤, true, <3, 1>, ?, 0)
5 September 2020 OSU CSE 21

Commutative Diagram
What concrete value represents that abstract value?
(≤, true, <3, 1>, ?, 0)
5 September 2020 OSU CSE 22

Commutative Diagram
What method body would do this (for any valid starting point)?
(≤, true, <3, 1>, ?, 0)
5 September 2020 OSU CSE 23

Another Useful Pseudo-Contract
* Reports whether a complete binary tree is a * heap.
* @requires
* [t is a complete binary tree]
* @ensures
* isHeap = [t is a heap]
public static boolean isHeap(BinaryTree t) {
5 September 2020 OSU CSE 24

Implementing isHeap • If|t| ≤ 1thentis a heap
• If|t| > 1thentis a heap iff:
– The root is ≤ the root of the left subtree
– The left subtree is a heap
– The root is ≤ the root of the right subtree (if any)
– The right subtree (if any) is a heap
5 September 2020 OSU CSE 25

Implementing isHeap
A smaller subproblem of
• If|t| ≤ 1thentis a heap
• If|t| > 1thentis a heap iff:
– The root is ≤ the root of the left subtree
– The left subtree is a heap
– The root is ≤ the root of the right subtree (if
– The right subtree (if any) is a heap
5 September 2020 OSU CSE 26
the same kind; a hint to use recursion.

Example: |t| > 1 x
5 September 2020
OSU CSE 27

Example: |t| > 1
If not, then t is not a heap.
If so, then check whether this subtree is a heap.
5 September 2020
OSU CSE 28

Example: |t| > 1 x
5 September 2020 OSU CSE

Is x ≤ y? Example: |t| > 1
If not, then t is not a heap.
If so, then check whether this subtree is a heap.
5 September 2020

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts