Week 9 of the course¶

Self-study¶

The topics for this week are (i) The heap data structure, (ii) Implementing a heap as an array

The following links will take you to the video-lectures and the accompanying slides:

The heap data structure¶

The heap data structure (part 1)

The heap data structure (part 2)

The heap data structure (part 3)

slides

Implementing a heap as an array¶

Implementing a heap as an array (part 1)

Implementing a heap as an array (part 2)

Implementing a heap as an array (part 3)

slides

Heap and heap operations¶

Question 1

In a max-heap having at least two nodes

the key of a leaf can be greater than the key of the root

it may be that the subtree of some node is not itself a max-heap

one can never be sure where the largest key will be in the binary tree

some leaf will have the smallest key in the binary tree

Question 2

A heap is a binary tree. Which of the following properties does a heap’s binary tree possess? (More than 1 property may be valid.)

For a fixed number of nodes, the height of a the binary tree is as small as possible.

All leaves are at the same depth.

There is at most one node that has exactly one child.

The number of leaves at a even depth must be even and the number of leaves at an odd depth must be odd.

At the lowest depth, each leaf must be the only child of its parent.

Question 3

Which of the following happens when we add a new node to a max-heap?

We initially add the new node as a leaf. If the new node’s key is less than the key of the root, the new node will always remain a leaf.

We replace the existing root with the new node. We then reinsert the old root as a leaf anywhere in the tree and we are done.

We initially add the new node as a leaf. For as long as the new node’s key is larger than the key of its parent, we allow the new node to move up in the binary tree.

If the key of the new node is greater than that of the root, then we simply replace the root with the new node and discard the old root.

Question 4

In which of the following situations would we need to use the Heapify algorithm in a max-heap?

when a node has only one child and we need it to have 2 children

when the root has a child whose key is larger than the root’s key

when the key of a leaf is smaller than the key of its parent

when keys of all the nodes are the same

Question 5

Regarding the Buildheap algorithm, which of the following are true? (More than 1 statement may be true.)

To work properly Buildheap needs to know what are the non-leaf nodes of the input binary tree.

Buildheap processes the nodes of binary tree using in a preorder ordering.

Buildheap starts by forming small heaps. It then progressively forms larger heaps until eventually it has formed one heap from the entire input binary tree.

Buildheap will only work properly if its input is a heap.

Question 6

What does the Heap-Extract-Max algorithm compute?

It obtains the largest key from the heap and it adds a new leaf whose key is equal to the largest key.

For some positive integer \(k\), the algorithm forms a new max-heap having the \(k\) largest keys from the input heap. (The input \(k\) is at most the number of nodes in the input heap.)

It removes from the input max-heap all nodes whose keys are less than the largest key in the heap.

From the input max-heap, it obtains the largest key. It then removes the root and re-forms the remaining nodes into a new max-heap.

Question 7

Consider the following four algorithms: Buildheap, Heap-Extract-Max, Heapify and Heap-Insert. Assume that the heap used as input to each algorithm has \(n\) nodes. Of these four algorithms, which have runtime efficiencies that are logarithmic in \(n\)?

Buildheap and Heap-Insert

Buildheap, Heap-Extract-Max, and Heap-Insert

Heap-Extract-Max, Heapify and Heap-Insert

Buildheap, Heap-Extract-Max and Heapify

A Heap as an array¶

Question 1

Suppose a binary tree max-heap is stored in an array \(A\). Suppose \(A[i]\) corresponds to node \(x\). Which of the following are true? (More than one statement may be true.)

If \(x\) is the root, then \(i\) is the the first position in \(A\).

Suppose \(x\) is not the root. There does not exist a function having constant runtime efficiency with which we can compute the position in \(A\) of the parent of \(x\).

If \(x\) has two children, then there exist functions having constant runtime efficiency with which we can compute the positions in \(A\) of the children of \(x\).

If the max-heap has \(n\) nodes, the position of the rightmost leaf in \(A\) can be anything between \(1\) and \(n\).

If the max-heap has \(n\) nodes, then \(A[n]\) is the smallest key occuring in the heap.

If \(x\) is a leaf, then there are only two possibilities for element \(A[i+1]\). Either \(A[i+1]\) corresponds to another leaf or \(A[i+1]\) does not correspond to any node because \(x\) is the rightmost leaf in the heap.

Question 2

Of the following, what are the advantages of Heapsort as an algorithm for sorting numbers? (More than one statement may be true.)

No extra storage space is needed to sort the elements in the heap.

When using Heapsort one need not know the actual number of elements in the heap.

It has the same big-O asymptotic runtime efficiency as other fast sorting algorithms such as Mergesort.

When using Heapsort it is possible to test in constant time if the heap is already completely sorted or not.

When using Heapsort, one never need multiply by 2 or divide by 2 which makes Heapsort run very fast.

Question 1

Formulate a central question for the course, which this week’s videos will cover give the answer.

Question 2

Which video topic should be discussed in particular in a discussion session?

Heap as a binary tree

Heap operations and their run efficiencies

Heap as an array

Heapsort

Question 3

Was there anything particularly difficult about the content of the videos? What about interesting? Something you’d like to learn more about?

Extra links on the topic:

Typically a priority queue is implemented as a binary tree heap. An alternative data structure that can be used for a priority queue is a binomial tree heap

Week09 - Glossary

Homework to be returned for the weekly exercises¶

Homework to be returned this week