search
Log In

Recent questions tagged heap

1 vote
3 answers
1
​​​​​Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$? $\Theta (1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
asked Feb 18 in DS Arjun 644 views
0 votes
1 answer
2
Consider the process of inserting an element into a $Max\ Heap$, where the $Max\ Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is $\Theta(\log _{2}n)$ $\Theta(n\log _{2} \log_2 n)$ $\Theta (n)$ $\Theta(n\log _{2}n)$
asked Apr 2, 2020 in DS Lakshman Patel RJIT 704 views
0 votes
2 answers
3
A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10,8,5,3,2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is $10,8,7,3,2,1,5$ $10,8,7,2,3,1,5$ $10,8,7,1,2,3,5$ $10,8,7,5,3,2,1$
asked Mar 30, 2020 in DS Lakshman Patel RJIT 193 views
0 votes
2 answers
4
Consider a complete binary tree where the left and the right sub trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: $\Omega(\log n)$ $\Omega(n\log n)$ $\Omega(n)$ $\Omega(n^2)$
asked Mar 30, 2020 in DS Lakshman Patel RJIT 355 views
0 votes
6 answers
5
Which of the following is a valid heap? $a$ $b$ $c$ $d$
asked Mar 24, 2020 in DS jothee 321 views
0 votes
1 answer
6
A 3 way (ternary) min heap is a 3 way ( ternary - each node as atmost three children nodes, left, mid, right ) complete tree with min heap property ( value of the parent is less than the value of the children ) satisfied at every node. Given a ternary ... function. (c) In Heapsort, binary heap is preferred over ternary heap. State if this statement is true or false, you must justify your answer.
asked Aug 27, 2019 in Algorithms Shaik Masthan 266 views
0 votes
0 answers
7
Give an $O(n\lg\ 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 minheap for $k$-way merging.)
asked Jun 27, 2019 in Algorithms akash.dinkar12 78 views
0 votes
1 answer
8
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.
asked Jun 27, 2019 in Algorithms akash.dinkar12 151 views
0 votes
0 answers
9
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.
asked Jun 27, 2019 in Algorithms akash.dinkar12 65 views
0 votes
0 answers
10
Each exchange operation on line $5$ of HEAP-INCREASE-KEY typically requires three assignments. Show how to use the idea of the inner loop of INSERTION-SORT to reduce the three assignments down to just one assignment.
asked Jun 27, 2019 in Algorithms akash.dinkar12 64 views
0 votes
0 answers
11
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant: At the start of each iteration of the while loop of lines $4-6$, the subarray $A[1..A.heapsize]$ satisfies the max-heap property, except that there may be one violation$::$ $A[i]$ may be ... $A[a..heapsize]$ satisfies the max-heap property at the time HEAP-INCREASE-KEY is called.
asked Jun 27, 2019 in Algorithms akash.dinkar12 51 views
0 votes
0 answers
12
Why do we bother setting the key of the inserted node to $-\infty$ in line $2$ of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
asked Jun 27, 2019 in Algorithms akash.dinkar12 102 views
0 votes
0 answers
13
Write pseudo code for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
asked Jun 27, 2019 in Algorithms akash.dinkar12 45 views
0 votes
0 answers
14
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAX-HEAP-INSERT(A,key) 1 A.heapsize = A.heapsize + 1 2 A[A.heapsize] ... -KEY(A,A.heapsize,key) Illustrate the operation of MAX-HEAP-INSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked Jun 27, 2019 in Algorithms akash.dinkar12 101 views
0 votes
0 answers
15
HEAP-EXTRACT-MAX(A) 1 if A.heap-size < 1 2 error “heap underflow” 3 max=A[1] 4 A[1]=A[A.heapsize] 5 A.heapsize=A.heapsize-1 6 MAX-HEAPIFY(A,1) 7 return max Illustrate the operation of HEAP-EXTRACT-MAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked Jun 27, 2019 in Algorithms akash.dinkar12 56 views
0 votes
0 answers
16
0 votes
0 answers
17
0 votes
0 answers
18
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?
asked Jun 27, 2019 in Algorithms akash.dinkar12 58 views
0 votes
0 answers
19
Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a max-heap containing the $i$ smallest elements of $A[1..n] $, and the subarray $A[i+1..n]$ contains the $n- i$ largest elements of $A[1..n]$, sorted.
asked Jun 27, 2019 in Algorithms akash.dinkar12 60 views
0 votes
0 answers
20
HEAPSORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAX-HEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
asked Jun 27, 2019 in Algorithms akash.dinkar12 125 views
0 votes
0 answers
21
0 votes
0 answers
22
Why do we want the loop index $i$ in line $2$ of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?
asked Jun 26, 2019 in Algorithms akash.dinkar12 51 views
0 votes
0 answers
23
BUILD-MAX-HEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAX-HEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILD-MAX-HEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle $
asked Jun 26, 2019 in Algorithms akash.dinkar12 168 views
0 votes
0 answers
24
Show that the worst-case running time of MAX-HEAPIFY on a heap of size $n$ is $\Omega(lg\ n)$.(Hint: For a heap with $n$ nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf).
asked Jun 26, 2019 in Algorithms akash.dinkar12 40 views
0 votes
0 answers
25
The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
asked Jun 26, 2019 in Algorithms akash.dinkar12 55 views
0 votes
0 answers
26
0 votes
0 answers
27
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
asked Jun 26, 2019 in Algorithms akash.dinkar12 37 views
...