# Chapter 10
## Exercise 10.1-1
**Available in the latest revision of the IM.**
## Exercise 10.1-2
## Exercise 10.1-3
**Available in the latest revision of the IM.**
## Exercise 10.1-4
## 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](https://www.happycoders.eu/algorithms/implement-deque-using-array/).
## Exercise 10.1-7
**Available in the latest revision of the IM.**
## Exercise 10.1-8
**Available in the latest revision of the IM.**
{% hint style="info" %}
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.
{% endhint %}
## 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.**
{% hint style="danger" %}
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`.
{% endhint %}
## Exercise 10.2-4
**Available in the latest revision of the IM.**
{% hint style="warning" %}
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.
{% endhint %}
## 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) |
{% hint style="info" %}
If we adorn a sorted, singly linked list with a *tail* pointer, then finding the maximum takes $$O(1)$$ time.
{% endhint %}
## Problem 10-2
I recommend reading the lecture notes in the attached PDF document about mergeable heaps (downloaded from [here](https://cse.sc.edu/~fenner/csce750/notes/notes-mergeable-heaps.pdf) 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.
{% file src="" %}
{% hint style="danger" %}
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.
{% endhint %}
## Problem 10-3
**Available in the latest revision of the IM.**