Heaps
The (binary) heap data structure is an array object that we can view as a nearly complete binary tree. Heapsort uses heap data structure to manage its information. In this article, we present one of the most popular applications of a heap: as an efficient priority queue. [1]
Usually, a priority queue has a contract with methods to insert an element into it, examine the head of the queue, and to remove the element at the head of the queue. Here’s our contract for the priority queue.
Next, we have to implement this contract. Here’s how it looks.
Now, we have the priority queue under our belt, we can go ahead and use it to solve real world problems. Even though it is much easier to come up with a slightly contrived example of using the priority queue, this time around, I thought of coming up with a more real example which showcases the real capabilities of our data structure. The beauty of this approach is that it pounds on the data structure so much and allows us to find any vulnerabilities in our implementation. This exercise was drawn from the book [1].
Exercises
6.5-9
Give an $Θ(n \cdot log_2\;k)-$time algorithm to merge k sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: Use a min-heap for $k-$way merging.)
We can get the first element of each list and insert it into a priority queue. Then, you can remove the smallest element from the queue, and insert another element off the list it came from. Here’s how it looks.
Analysis
The running time of extract is $log_2 n$. The running time of insert on an $n-$element heap is $log_2\; n$.
For $k-$way merging, in each iteration, we remove the smallest element from the priority queue and insert another element off the list it came from. This takes $log_2\;k$ at each step of the iteration. Thus, total time it takes to merge the lists is, $Θ(n \cdot log_2\;k)$.
Let $n$ be the number of elements in all the lists, let $k$ be the number of sorted lists and $T(n)$ be the running time of the procedure. Thus,
$$\Large T(n) = Θ(n \cdot 2 \cdot log_2k) = Θ(n \cdot log_2k)$$
Runtime analysis of BUILD-MAX-HEAP algorithm
$$\sum_{h=0}^{\lfloor log_2 n \rfloor} \left \lceil \frac{n}{2^{h+1}} \right \rceil \cdot Θ(h)$$
rewriting the equation, we then obtain
$$Θ\left(n \cdot \sum_{h=0}^{\lfloor log_2 n \rfloor} \frac{h}{2^{h+1}}\right) \lt Θ\left(\frac {n}{4} \cdot \sum_{h=0}^{\infty} \frac{h}{2^{h-1}}\right) \equiv Θ\left(\frac {n}{4} \cdot \sum_{h=0}^{\infty} h \cdot \left( \frac {1}{2} \right) ^{h-1} \right) $$
Now by plugging in $x = \frac {1}{2}$ we obtain,
$$Θ\left(\frac {n}{4} \cdot \sum_{h=0}^{\infty} h \cdot x ^{h-1} \right) \equiv Θ\left(\frac {n}{4} \cdot \frac{d}{dx} \sum_{h=0}^{\infty} x ^{h} \right)$$
Now, we know that
$$\sum_{n=0}^{\infty} x^{n} = \frac {1}{1-x}$$
Thus, the above equation can be further simplified as follows.
$$Θ\left(\frac {n}{4} \cdot \frac{d}{dx} \sum_{h=0}^{\infty} x ^{h} \right) \equiv Θ\left(\frac {n}{4} \cdot \frac{d}{dx} \frac {1}{1-x} \right)$$
Finding the derivative using the chain rule yields:
$$\frac{d}{dx} \frac {1}{1-x} \equiv \frac{d}{dx} \left(1-x \right)^{-1} = \frac{1}{\left( {1-x} \right) ^ {2}}$$
Plugging this in our original equation, we then obtain,
$$Θ\left(\frac {n}{4} \cdot \frac{d}{dx} \frac {1}{1-x} \right) \equiv Θ\left(\frac {n}{4} \cdot \frac{1}{\left( {1-x} \right) ^ {2}} \right)$$
Finally, by plugging in $x = \frac {1}{2}$ we obtain,
$$Θ\left(\frac {n}{4} \cdot \frac{1}{\left( {1-x} \right) ^ {2}} \right) = Θ\left(\frac {n}{4} \cdot \frac{1}{\left( {1- \frac{1}{2}} \right) ^ {2}} \right) = Θ\left(n \right)$$
Comments
Post a Comment