# 10.3: Discussion and Exercises

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\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]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

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

The randomized MeldableHeap data structure described here appears to have first been proposed by Gambin and Malinowski [34]. Other meldable heap implementations exist, including leftist heaps [16,48, Section 5.3.2], binomial heaps [75], Fibonacci heaps [30], pairing heaps [29], and skew heaps [72], 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 [25]. This more efficient $$\mathtt{decreaseKey(u,y)}$$ operation has applications in speeding up several graph algorithms, including Dijkstra's shortest path algorithm [30].

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) .