CHAPTER 6
Priority Queues (Heaps)
6.2
6.3 The result of three deleteMins, starting with both of the heaps in Exercise 6.2, is as follows:
6.4 (a) 4N
6.5
/**
* Insert item x, allowing duplicates.
*/
6.6 225. To see this, start with i = 1 and position at the root. Follow the path toward the last node, doubling i
6.7 (a) We show that H(N), which is the sum of the heights of nodes in a complete binary tree of N nodes, is
N − b(N), where b(N) is the number of ones in the binary representation of N. Observe that for N = 0 and
The second line follows from the inductive hypothesis, and the third follows because L + R = N − 1. Now the
If the last node is in the right subtree, then
( ) logb L N=
. The binary representation of R is identical to
(b) Run a single-elimination tournament among eight elements. This requires seven comparisons and
generates ordering information indicated by the binomial tree shown here.
(c) A recursive strategy is used. Assume that N = 2k. A binomial tree is built for the N elements as in part (b).
The largest subtree of the root is then recursively converted into a binary heap of 2k − 1 elements. The last
6.8 a) Since each element in a min heap has children whose elements are greater than the value in the
6.9 Let D1, D2, . . . ,Dk be random variables representing the depth of the smallest, second smallest, and kth
smallest elements, respectively. We are interested in calculating E(Dk). In what follows, we assume that the
Lemma.
Proof.
An element that is at depth d in the left subheap is at depth d + 1 in the entire subheap. Since
E(Dj + 1) = E(Dj) + 1, the theorem follows.
Theorem.
Proof.
The proof is by induction. The theorem clearly holds for k = 1 and k = 2. We then show that it holds for
arbitrary k > 2 on the assumption that it holds for all smaller k. Now, by the inductive hypothesis, for any
1
,
1
( ) ( ( ) +1)
k
k j k j
j
E D p E D
−
=
=
6.13 (a) If the heap is organized as a (min) heap, then starting at the hole at the root, find a path down to a leaf by
(b) Find a path of minimum children, stopping after log N − log log N levels. At this point, it is easy to
6.15 (a) O((M + d N) logd N).
6.16 Starting from the second most signficant digit in i, and going toward the least significant digit, branch left for
(c) SKETCH: Split the larger subheap into smaller heaps as follows: on the left-most path, remove two
b. Place the new element in the last open position (as in a regular heap). Now compare it to its parent. Now if
c) For a min deletion, remove the root . Let the last element in the heap be x . If the root has no children, then
6.22 If elements are inserted in decreasing order, a leftist heap consisting of a chain of left children is formed. This
6.23 (a) If a decreaseKey is performed on a node that is very deep (very left), the time to percolate up would be
prohibitive. Thus the obvious solution doesn’t work. However, we can still do the operation efficiently by a
6.24 Lazy deletion in leftist heaps is discussed in the paper by Cheriton and Tarjan [10]. The general idea is that if
6.25 (a) The standard way to do this is to divide the work into passes. A new pass begins when the first element
(b) It generates heaps that are more leftist.
6.30 Clearly the claim is true for k = 1. Suppose it is true for all values i = 1, 2, . . . , k. A Bk + 1 tree is formed by
6.31 Proof is by induction. Clearly the claim is true for k = 1. Assume true for all values i = 1, 2, . . . ,k. A Bk + 1
6.32
6.34
template<typename Comparable>
struct BiQueNode
{
private:
vector<BiQueNode<Comparable>> biQue;
};
template <typename Comparable>
BiQueNode<Comparable> * combine(BiQueNode<Comparable> * p, BiQueNode<Comparable> * q)
{
if (p–>item < q->item)
}
}
template <typename Comparable>
BiQueNode<Comparable> * insert(Comparable v)
{
BiQueNode<Comparable> * t = new BiQueNode<Comparable> v;
BiQueNode<Comparable> * c = t;
for (int i = 0; i <= biQue.size(); i++)
{
6.37
/*
Bin packing
private:
vector<double> bins;
priority_queue<double> heapBins;
public:
Bins(int size = 0)
{bins.resize(size);
for (int i = 0; i < size; i++)
bins[i] = 0;
}
bins.push_back(item);
}
int insertWorstFit(double item) // b
{
static int size = 0;
double maxRoom;
if (heapBins.empty())
heapBins.push(Cap – item);
else
heapBins.pop();
heapBins.push(maxRoom – item);
}
else
{heapBins.push(Cap – item);
size++;
{
for (int i = 0; i < bins.size(); i++)
if (bins[i]+item < Cap && bins[i]+item < gap)
{
gap = Cap – bins[i] – item;
gapIndex = i;
}
6.38 Don’t keep the key values in the heap, but keep only the difference between the value of the key in a node