Algorithms and Complexity (Heapsort) - Gate CSE

Heapsort’s running time is O(n lg n) Like insertion sort, but unlike merge sort, heapsort sorts in place i.e. only a constant number of array elements are stored outside the input array at any time.
The (binary) heap data structure is an array object that we can view as a nearly complete binary tree
The tree is completely ﬁlled on all levels except possibly the lowest, which is ﬁlled from the left up to a point.
An array A that represents a heap is an object with two attributes: A.length, which gives the number of elements in the array, and A.heap-size, which represents how many elements in the heap are stored within array A.
Although A[1 ... A.length] may contain numbers, only the elements in A[1 .. A.heap-size], where 0 ≤ A.heap-size ≤ A.length, are valid elements of the heap.
The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of its parent, left child, and right child

Parent index: floor(i/2) i.e. 3/2 = 1 and not 2.
Left node index: 2i
Right node index: 2i + 1

There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property:

Max heap: A[PARENT(i)] ≥ A[i] ; for every node other than root. Thus, the largest element in a max-heap is stored at the root
Min heap: A[PARENT(i)] ≤ A[i] ; The smallest element in a min-heap is at the root.

For the heapsort algorithm, we use max-heaps. Min-heaps commonly implement priority queues

Properties of a Heap

Height of a node in a heap is the number of edges on the longest simple downward path from the node to a leaf, and we define the height of the heap to be the height of its root.

Since a heap of n elements is based on a complete binary tree, its height is Θ(lg n).

The basic operations on heaps run in time at most proportional to the height of the tree and thus take O(lg n) time.

Solved Examples on Heaps.

Q. What are the minimum and maximum numbers of elements in a heap of height h?

At least \(2^h\) and at most \(2^{h+1} - 1\). Can be seen because a complete binary tree of depth h - 1 has \( \sum_{i=0}^{h-1} 2^i = 2^h - 1\) elements, and the number of elements in a heap of depth h is between the number for a complete binary tree of depth h - 1 exclusive and the number in a complete binary tree of depth h inclusive.

Ans . At least \(2^h\) and at most \(2^{h+1} - 1\)

Q. Show that an n-element heap has height ⌊lg n⌋.

Write n = 2^m - 1 + k where m is as large as possible. Then the heap consists of a complete binary tree of height m - 1, along with k additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these k leaves, which must have length m. It is clear from the way we defined m that m = ⌊lg n⌋

Q. Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurrin g anywhere in that subtree.

If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree. So, it is larger than it's parent, so, the heap property is violated at the parent of the maximum element in the subtree

Q. Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

The smallest element must be a a leaf node. Suppose that node x contains the smallest element and x is not a leaf. Let y denote a child node of x. By the max-heap property, the value of x is greater than or equal to the value of y. Since the elements of the heap are distinct, the inequality is strict. This contradicts the assumption that x contains the smallest element in the heap.

Q. Is an array that is in sorted order a min-heap?

Yes, it is. The index of a child is always greater than the index of the parent, so the heap property is satisfied at each vertex.

Q. Is the array with values {23; 17; 14; 6; 13; 10; 1; 5; 7; 12} a max-heap?

No, the array is not a max-heap. 7 is contained in position 9 of the array, so its parent must be in position 4, which contains 6. This violates the max-heap property.

Q. Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by ⌊n/2⌋ + 1, ⌊n/2⌋ + 2, ..., n.

It suffices to show that the elements with no children are exactly indexed by {⌊n/2⌋ + 1, ... ,n}. Suppose that we had an i in this range. It's children would be located at 2i and 2i + 1 but both of these are ≥ 2⌊n/2⌋+ 2 > n and so are not in the array. Now, suppose we had an element with no kids, this means that 2i and 2i + 1 are both > n, however, this means that i > n/2.

This means that i ∈ {⌊n/2⌋ + 1, ... ,n}.

In order to maintain the max-heap property, we call the procedure MAX-HEAPIFY. Its inputs are an array A and an index 'i' into the array.

When it is called, MAX-HEAPIFY assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are maxheaps, but that A[i] might be smaller than its children, thus violating the max-heap property.

MAX-HEAPIFY lets the value at A[i] “ﬂoat down” in the max-heap so that the subtree rooted at index i obeys the max-heap property.

```
MAX-HEAPIFY(A,i)
```
```
i = LEFT(i)
```
```
r = RIGHT(i)
```
```
if l ≤ A.heapsize and A[l] > A[i]
```
```
    largest = l
```
```
else largest = i
```

if r ≤ A.heapsize and A[r] > A[largest]

```
    largest = r
```
```
if largest ≠ i
```
```
    exchange A[i] with A[largest]
```
```
    MAX-HEAPIFY(A,largest)
```

```
PARENT(i)
```
```
   return ⌊i/2⌋
```

```
LEFT(i)
```
```
   return 2i
```

```
RIGHT(i)
```
```
   return 2i + 1
```

```
HEAPSORT(A)
```
```
BUILD-MAX-HEAP(A)
```
```
for i = ⌊A.length/2⌋ downto 1
```
```
   MAX-HEAPIFY(A,i)
```

```
BUILD-MAX-HEAP(A)
```
```
A.heapsize = A.length
```
```
for i = A.length downto 1
```
```
   exchange A[1] with A[i]
```
```
   A.heapsize = A.heapsize - 1
```
```
   MAX-HEAPIFY(A,1)
```

Working of MAX-HEAPIFY

At each step, the largest of the elements A[i], A[LEFT(i)],and A[RIGHT(i)] is determined, and its index is stored in largest
If A[i] is largest, then the subtree rooted at node i is already a max-heap and the procedure terminates. Otherwise, one of the two children has the largest element, and A[i] is swapped with A[largest], which causes node i and its children to satisfy the max-heap property. The node indexed by largest,however, now has the original value A[i], and thus the subtree rooted at largest might violate the max-heap property. Consequently, we call MAX-HEAPIFY recursively on that subtree.
The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the Θ(1) time to fix up the relationships among the elements A[i], A[LEFT(i)] , and A[RIGHT(i)] , plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i (assuming that the recursive call occurs).
The children’s subtrees each have size at most 2n/3 - the worst case occurs when the bottom level of the tree is exactly half full and therefore we can describe the running time of MAX-HEAPIFY by the recurrence:
T(n) ≤ T(2n/3) + Θ(1) which is O(lg n). Alternatively, we can characterize the running time of MAX-HEAPIFY on a node of height h as O(h).

Flow of MAX-HEAPIFY

The initial conﬁguration is, with A[2] at node i = 2 violating the max-heap property since it is not larger than both children.
The max-heap property is restored for node 2 in (b) by exchanging A[2] with A[4], which destroys the max-heap property for node 4.
The recursive call MAX-HEAPIFY(A,4) now has i = 4. After swapping A[4] with A[9], as shown in (c), node 4 is ﬁxed up, and the recursive call MAX-HEAPIFY(A,9) yields no further change to the data structure.

Solved Questions on MAX-HEAPIFY

Q. Illustrate the operation of MAX-HEAPIFY(A,3) on the array A = {27; 17; 3; 16; 13; 10; 1; 5; 7; 12; 4; 8; 9; 0}.

Q. Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A,i), which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAX-H EAPIFY?

The running time of MIN-HEAPIFY is the same as that of MAX-HEAPIFY.

```
Algorithm 1: MIN-HEAPIFY(A,i)
```

```
l = LEFT(i)
```

```
r = RIGHT(i)
```

if l ≤ A.heapsize and A[l] < A[i] then

```
    smallest = l
```

```
else smallest = i
```

```
end if
```

if r ≤ A.heapsize and A[r] < A[smallest] then

```
    smallest = r
```

```
end if
```

```
if smallest ≠ i then
```

```
    exchange A[i] with A[smallest]
```

```
    MAX-HEAPIFY(A, smallest)
```

```
end if
```

Q. What is the effect of calling MAX-HEAPIFY(A,i) when the element A[i] is larger than its children?

The array remains unchanged since the if statement on line line 8 will be false.

Q. The operation of BUILD-MAX-HEAP for A = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}

Fig (a) has A 10-element input array A and the binary tree it represents. The ﬁgure shows that the loop index i refers to node 5 before the call MAX-HEAPIFY(A,i).

Fig (b) The data structure that results. The loop index i for the next iteration refers to node 4.

Fig (c)–(e) show Subsequent iterations of the for loop in BUILD-MAX-HEAP. Observe that whenever MAX-HEAPIFY is called on a node, the two subtrees of that node are both max-heaps. Fig. (f) The max-heap after BUILD-MAX-HEAP ﬁnishes.

Q. Runtime of Heapsort

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-MAXHEAP takes time O(n) and each of the n - 1 calls to MAX-HEAPIFY takes time O(lg n).

Q. Show operation of HEAPSORT on A = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}

Fig (a) The max-heap data structure just after BUILD-MAXHEAP has built it. Fig(b)–(j) The max-heap just after each call of MAX-HEAPIFY in line 5, showing the value of i at that time. Only lightly shaded nodes remain in the heap.

Fig (k) The resulting sorted array A.

Q. What is the running time of HEAPSORT on an array A of length n that is already sorted in increasing order? What about decreasing order?

If it's already sorted in increasing order, doing the build max heap-max-heap call on line 1 will take Θ(n lg(n)) time. There will be n iterations of the for loop, each taking Θ(lg(n)) time because the element that was at position i was the smallest and so will have ⌊lg(n)⌋ steps when doing max-heapify on line 5. So, it will be Θ(n lg(n)) time.

If it's already sorted in decreasing order, then the call on line one will only take Θ(n) time, since it was already a heap to begin with, but it will still take n lg(n) peel of the elements from the heap and re-heapify.

A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key.

Priority queue is the most popular application of a heap: as an efﬁcient priority queue. As with heaps, priority queues come in two forms: max-priority queues and min-priority queues.

Max-priority queues are in turn based on max-heaps

A max-priority queue supports the following operations:

INSERT(S,x) inserts the element x into the set S, which is equivalent to the operation S = S ∪ {x}

MAXIMUM(S) returns the element of S with the largest key.

EXTRACT-MAX(S) removes and returns the element of S with the largest key.

INCREASE-KEY(S,x,k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value.
A max-priority queue is to schedule jobs on a shared computer. The max-priority queue keeps track of the jobs to be performed and their relative priorities. When a job is ﬁnished or interrupted, the scheduler selects the highest-priority job from among those pending by calling EXTRACT-MAX. The scheduler can add a new job to the queue at any time by calling INSERT.

min-priority queue supports the operations INSERT, MINIMUM, EXTRACT-MIN, and DECREASE-KEY. A min-priority queue can be used in an event-driven simulator. The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future. The simulation program calls EXTRACT-MIN at each step to choose the next event to simulate. As new events are produced, the simulator inserts them into the min-priority queue by calling INSERT.

Operations of a max-priority queue

```
HEAP-MAXIMUM(A)
```
```
return A[1]
```

```
HEAP-EXTRACT-MAX(A)
```
```
if A.heap-size < 1
```
```
    error “heap underﬂow”
```
```
max = A[1]
```
```
A[1] =  A.[heap-size] - 1
```
```
MAX-HEAPIFY(A,1)
```
```
return max
```

The running time of HEAP-EXTRACT-MAX is O(lg n), since it performs only a constant amount of work on top of the O(lg n) time for MAX-HEAPIFY.

HEAP-INCREASE-KEY

An index i into the array identiﬁes the priority-queue element whose key we wish to increase. The procedure ﬁrst updates the key of element A[i] to its new value.

Because increasing the key of A[i] might violate the max-heap property, the procedure then traverses a simple path from this node toward the root to ﬁnd a proper place for the newly increased key.

As HEAP-INCREASE-KEY traverses this path, it repeatedly compares an element to its parent, exchanging their keys and continuing if the element’s key is larger, and terminating if the element’s key is smaller, since the max-heap property now holds.

```
HEAP-INCREASE-KEY(A,i,key)
```
```
if key < A[i]
```

    error “new key is smaller than current key”

```
A[i] = key
```
```
while i > 1and A[PARENT(i)] < A[i]
```
```
    exchange A[i] with A[PARENT(i)]
```
```
    i = PARENT(i)
```

The running time of HEAP-INCREASE-KEY on an n-element heap is O(lg n), since the path traced from the node updated in line 3 to the root has length O(lg n).

MAX-HEAP-INSERT

It takes as an input the key of the new element to be inserted into max-heap A. The procedure first expands the max-heap by adding to the tree a new leaf whose key is -∞.

Then it calls HEAP-INCREASE-KEY to set the key of this new node to its correct value and maintain the max-heap property.

The running time of MAX-HEAP-INSERT on an n-element heap is O(lg n). In summary, a heap can support any priority-queue operation on a set of size n in O(lg n) time.

```
MAX-HEAP-INSERT(A, key)
```
```
A.heap-size = A.heap-size + 1
```
```
A[A.heap-size] = - ∞
```
```
HEAP-INCREASE-KEY(A, A.heapsize, key)
```

Q. Illustrate the operation of HEAP-EXTRACT-MAX on the heap A = {15; 13; 9; 5; 12;8;7;4;0;6;2;1} .

Q.Illustrate the operation of MAX-HEAP-INSERT(A,10) on the heap A = {15; 13; 9; 5;12;8;7;4;0;6;2;1}.

Q.The operation HEAP-DELETE(A,i) deletes the item in node i from heap A.Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

The algorithm works as follows: Replace the node to be deleted by the last node of the heap. Update the size of the heap, then call MAX-HEAPIFY to move that node into its proper position and maintain the max-heap property. This has running time O(lg n) since the number of times MAX-HEAPIFY is recursively called is as most the height of the heap, which is ⌊ lg n⌋

```
Algorithm 2: HEAP-DELETE(A,i)
```
```
A[i] = A[A.heapsize]
```
```
A.heapsize = A.heapsize + 1
```
```
MAX-HEAPIFY(A,i)
```

Q.4 Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is.(Gate 2015 Set1)

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Ans (B)

The given graph is undirected, so an edge (u, v) also means (v, u) is also an edge. Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference between d(u) and d(v) can not be more than 1.

Q. 4 A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _____. (GATE 2016 SET B)

Ans . 8

Solution steps: n^th smallest element will be present within n levels of min heap.

Q. The number of elements that can be sorted in \(\theta(\log n)\) time using heap sort is (GATE 2013 SET D)

\(\theta(1)\)

\(\theta(\sqrt{\log n}) \)

\(\theta(\frac{\log n}{\log\log n}) \)

\(\theta(\log n)\)

Ans . 1

After constructing a max-heap in the heap sort , the time to extract maximum element and then heapifying the heap takes \(\theta(\log n)\) time by which we could say that \(\theta(\log n)\) time is required to correctly place an element in sorted array. If \(\theta(\log n)\) time is taken to sort using heap sort, then number of elements that can be sorted is constant which is \(\theta(1)\)

Common Data Question
The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed

void find_and_replace (char *A, char *oldc, char *newc) {

```
   for (int  i =0; i < 5; i++)
```
```
        for(int j=0; j < 3; j++)
```
```
            if(A[i] == oldc[j])
```
```
                A[i]=newc[j];
```
```
}
```

The procedure is tested with the following four test cases (GATE 2013 SET D)

oldc = "abc",newc = "dab"

oldc = "cde",newc = "bcd"

oldc = "bca",newc = "cda"

oldc = "abc",newc = "bac"

Q. The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw? (GATE 2013 SET D)

Only one

Only two

Only three

All four

Ans . 2

Flaw in this given procedure is that one character of Array ‘A’ can be replaced by more than one character of newc array, which should not be so.Test case (3) and (4) identifies this flaw as they are containing ‘oldc’ and ‘newc’ array characters arranged in specific manner. Following string can reflect flaw, if tested by test case (3).
initially i = j= 0
A="bcda" oldc="bca" newc="cda"
b=b so replaced by c
Next i = 0 and j=1
A="ccda" oldc="bca" newc="cda"
c=c so replaced by d
Likewise single character ‘b’ in A is replaced by ‘c’ and then by ‘d’.
Same way test case (4) can also catch the flaw

Q. If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure? (GATE 2013 SET D)

None

2 Only

3 and 4 only

4 only

Ans . 3

Now for string “abcde” in array A, both test case (3) and (4) will be successful in finding the flaw, as explained in above question.

Q.4 A max-heap is a heap where the value of each parent is greater than or equal to the values of its children. Which of the following is a max-heap? (GATE 2011)

Ans . (B)

A is not a max-heap because it is not a complete binary tree
B is a max-heap because it is complete binary tree and follows max-heap property.
C is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property.
D is not a max-heap because 8 is a chile of 5 in this tree, so violates the max-heap property. There are many other nodes in this tree which violate max-heap property in this tree.

Q.We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is(GATE Paper-2008)

θ (logn)

θ(n)

θ(nlogn)

θ(n^2)

Ans . (2)

Explanation :

The worst case time complexity for insertion in a binary heap is O(Logn). So inserting n elements in a heap of size n should take θ(nlogn) time. But choice (2) seems to be more appropriate answer. One of the solution of O(n) complexity can be to take the ‘n’ elements of the heap and other ‘n’ elements together and construct heap in O(2n) = O(n).

Q. Assuming there are n keys and each keys is in the range [0, m-1]. The run time of bucket sort is (UGC-NET 2013)

O(n)

O(n lgn)

O(n lgm)

O(n+m)

Ans . 4

The complexity of bucket sort isn’t constant depending on the input. However in the average case the complexity of the algorithm is O(n + k) where n is the length of the input sequence, while k is the number of buckets.

Q.3The time complexity of recurrence relation T(n) = T(n/3) + T(2n/3) + O(n) is(UGC-NET 2013)

O(Ig n)

O(n)

O(n Ig n)

O(n² )

Ans . 3

Q.4The time complexity of an efficient algorithm to find the longest monotonically increasing subsequence of n numbers is(UGC-NET 2013)

O(n)

O(n lg n)

O(n²)

None of the above

Ans . 2

Q.5Given two sorted list of size ‘m’ and ‘n’ respectively. The number of comparison needed in the worst case by the merge sort algorithm will be (UGC-NET 2013)

m x n

max (m, n)

min (m, n)

m + n – 1

Ans . 3

Q.6Let A and B be two n x n matrices. The efficient algorithm to multiply the two matrices has the time complexity (UGC-NET 2013)

O(n³)

O(n^2.81)

O(n^2.67)

O(n²)

Ans . 2

Strassens matrix multiplication algorithm

Q. Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is (GATE 2001)

i – 1

floor(i/2)

ceiling(i/2)

(i+1)/2

Ans. 2

Binary heaps can be represented using arrays: storing elements in an array and using their relative positions within the array to represent child-parent relationships. For the binary heap element stored at index i of the array,
Parent Node will be at index: floor(i/2)
Left Child will be at index: 2i
Right child will be at index: 2*i + 1

1. In a binary max heap containing n numbers, the smallest element can be found in time (GATE 2006)

O(n)

O(Logn)

O(log(logn))

O(1)

Ans . (A) O(n)

In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n).
            12
         /        \
       /         \
    8             7
   /     \        /      \
  /      \      /       \
2         3 4      5

UPSCFEVER - POPULAR PAGES

Join The Movement

Share

upscfever.com

Discussions and Comments

Journey of a Thousand Miles begins with One Click!!!

Heapsort

Heap Sort Algorithm

Priority Queues

Solved Questions

Solved Question Papers

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments