Chapter 10

Exercise 10.1-1

Available in the latest revision of the IM.

Exercise 10.1-2

Illustration of stack operations, where items in red are returned from a Pop function.

Exercise 10.1-3

Available in the latest revision of the IM.

Exercise 10.1-4

Illustration of queue operations, where items in red are returned from a Dequeue function and those in blue are garbage.

Exercise 10.1-5

Available in the latest revision of the IM.

Exercise 10.1-6

A detailed treatment of this topic is available here.

Exercise 10.1-7

Available in the latest revision of the IM.

Exercise 10.1-8

Available in the latest revision of the IM.

It is also possible to switch the running times by letting Push execute in $\Theta(n)$ time and Pop in $O(1)$. We need two labels for queues: primary and auxiliary.Suppose the former is $Q_1$ and the latter is $Q_2$ when a new elements is pushed onto a stack. It should go into $Q_2$ and afterward the content of $Q_1$ needs to be poured into $Q_2$. Finally, the labels should be swapped. The Pop operation simply reads the next element from a primary queue.

Exercise 10.2-1

Available in the latest revision of the IM.

Exercise 10.2-2

Available in the latest revision of the IM.

Exercise 10.2-3

Available in the latest revision of the IM.

The solution in the IM is incorrect. After adding the new attribute L.tail, the Enqueue operation should be implemented by List-Append(L, x) and Dequeue by List-Delete(L, L.head). The proposed List-Delete(L, L.tail) takes $\Theta(n)$ in the worst case, since we need to find the predecessor of L.tail.

Exercise 10.2-4

Available in the latest revision of the IM.

The solution in the IM only works when both $S_1$ and $S_2$ are nonempty. Furthermore, using a singly linked list, adorned with a tail pointer, is a much leaner data structure than a circular, doubly linked list with a sentinel.

Exercise 10.2-5

Available in the latest revision of the IM.

Exercise 10.2-6

Available in the latest revision of the IM.

Exercise 10.3-1

       15
       / \
      /   \
     /     \
    /       \
   17       20
   / \      /
 22  13    25
     / \     \
    12 28    33
             /
            14

Exercise 10.3-2

Available in the latest revision of the IM.

Exercise 10.3-3

Available in the latest revision of the IM.

Exercise 10.3-4

Available in the latest revision of the IM.

Exercise 10.3-5

Available in the latest revision of the IM.

Exercise 10.3-6

Available in the latest revision of the IM.

Problem 10-1

	unsorted, singly linked	sorted, singly linked	unsorted, doubly linked	sorted, doubly linked
Search	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$
Insert	$O(1)$	$\Theta(n)$	$O(1)$	$\Theta(n)$
Delete	$\Theta(n)$	$\Theta(n)$	$O(1)$	$O(1)$
Successor	$\Theta(n)$	$O(1)$	$\Theta(n)$	$O(1)$
Predecessor	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	$O(1)$
Minimum	$\Theta(n)$	$O(1)$	$\Theta(n)$	$O(1)$
Maximum	$\Theta(n)$	$\Theta(n)^*$	$\Theta(n)$	$O(1)$

If we adorn a sorted, singly linked list with a tail pointer, then finding the maximum takes $O(1)$ time.

Problem 10-2

I recommend reading the lecture notes in the attached PDF document about mergeable heaps (downloaded from here on October 2025). It introduces a binomial heap, as specific variant of mergeable heap, that also supports two additional operations: decreasing a key of some node and deleting a node. Essentially, the text follows Problem 19-2 from the 3rd edition of the book. For a deep dive into this topic, you might want to read chapter 19 from the previous edition of the book, which is freely downloadable from the book's official website.

211KB

notes-mergeable-heaps.pdf

PDF

Open

There is a bug in the implementation of MergeTree.The first two lines should be changed to read as follows:

if T1.key > T2.key:
    swap(T1, T2) // Pointer swap; now T1.key < T2.key.

Problem 10-3

Available in the latest revision of the IM.