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

Before wind up, let’s analyze the running time of the BUILD-MAX-HEAP algorithm. Our tighter analysis relies on the properties that an n-element heap has height $\lfloor log_2(n)\rfloor$ and at most $\LARGE \lceil \frac{n}{2^{h+1}} \rceil$ nodes of any height $h$. The time required by MAX-HEAPIFY when called on a node of height $h$ is $Θ(h)$, and so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by [1] [2]


$$\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

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour
Read more