# 10.3: Discussion and Exercises

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

The implicit representation of a complete binary tree as an array, or list, seems to have been first proposed by Eytzinger . He used this representation in books containing pedigree family trees of noble families. The BinaryHeap data structure described here was first introduced by Williams .

The randomized MeldableHeap data structure described here appears to have first been proposed by Gambin and Malinowski . Other meldable heap implementations exist, including leftist heaps [16,48, Section 5.3.2], binomial heaps , Fibonacci heaps , pairing heaps , and skew heaps , although none of these are as simple as the MeldableHeap structure.

Some of the above structures also support a $$\mathtt{decreaseKey(u,y)}$$ operation in which the value stored at node $$\mathtt{u}$$ is decreased to $$\mathtt{y}$$. (It is a pre-condition that $$\mathtt{y}\le\texttt{u.x}$$.) In most of the preceding structures, this operation can be supported in $$O(\log \mathtt{n})$$ time by removing node $$\mathtt{u}$$ and adding $$\mathtt{y}$$. However, some of these structures can implement $$\mathtt{decreaseKey(u,y)}$$ more efficiently. In particular, $$\mathtt{decreaseKey(u,y)}$$ takes $$O(1)$$ amortized time in Fibonacci heaps and $$O(\log\log \mathtt{n})$$ amortized time in a special version of pairing heaps . This more efficient $$\mathtt{decreaseKey(u,y)}$$ operation has applications in speeding up several graph algorithms, including Dijkstra's shortest path algorithm .

Exercise $$\PageIndex{1}$$

Illustrate the addition of the values 7 and then 3 to the BinaryHeap shown at the end of Figure 10.1.2.

Exercise $$\PageIndex{2}$$

Illustrate the removal of the next two values (6 and 8) on the BinaryHeap shown at the end of Figure 10.1.3.

Exercise $$\PageIndex{3}$$

Implement the $$\mathtt{remove(i)}$$ method, that removes the value stored in $$\mathtt{a[i]}$$ in a BinaryHeap. This method should run in $$O(\log \mathtt{n})$$ time. Next, explain why this method is not likely to be useful.

Exercise $$\PageIndex{4}$$

A $$d$$-ary tree is a generalization of a binary tree in which each internal node has $$d$$ children. Using Eytzinger's method it is also possible to represent complete $$d$$-ary trees using arrays. Work out the equations that, given an index $$\mathtt{i}$$, determine the index of $$\mathtt{i}$$'s parent and each of $$\mathtt{i}$$'s $$d$$ children in this representation.

Exercise $$\PageIndex{5}$$

Using what you learned in Exercise $$\PageIndex{4}$$, design and implement a DaryHeap, the $$d$$-ary generalization of a BinaryHeap. Analyze the running times of operations on a DaryHeap and test the performance of your DaryHeap implementation against that of the BinaryHeap implementation given here.

Exercise $$\PageIndex{6}$$

Illustrate the addition of the values 17 and then 82 in the MeldableHeap $$\mathtt{h1}$$ shown in Figure 10.2.1. Use a coin to simulate a random bit when needed.

Exercise $$\PageIndex{7}$$

Illustrate the removal of the next two values (4 and 8) in the MeldableHeap $$\mathtt{h1}$$ shown in Figure 10.2.1. Use a coin to simulate a random bit when needed.

Exercise $$\PageIndex{8}$$

Implement the $$\mathtt{remove(u)}$$ method, that removes the node $$\mathtt{u}$$ from a MeldableHeap. This method should run in $$O(\log \mathtt{n})$$ expected time.

Exercise $$\PageIndex{9}$$

Show how to find the second smallest value in a BinaryHeap or MeldableHeap in constant time.

Exercise $$\PageIndex{10}$$

Show how to find the $$k$$th smallest value in a BinaryHeap or MeldableHeap in $$O(k\log k)$$ time. (Hint: Using another heap might help.)

Exercise $$\PageIndex{11}$$

Suppose you are given $$\mathtt{k}$$ sorted lists, of total length $$\mathtt{n}$$. Using a heap, show how to merge these into a single sorted list in $$O(n\log k)$$ time. (Hint: Starting with the case $$k=2$$ can be instructive.)

This page titled 10.3: Discussion and Exercises is shared under a CC BY license and was authored, remixed, and/or curated by Pat Morin (Athabasca University Press) .