Skip to main content
6 votes
Accepted

When the heapsort worst case occurs?

Please check the paper@arXiv2015: A Complete Worst-Case Analysis of Heapsort by M. A. Suchenek. This paper gives a rather involved lower bound; see Abstract and Theorem 12.2 on page 94. To the ...
hengxin's user avatar
  • 9,561
3 votes
Accepted

Is it possible to sort this type of array in O(n) time?

It does not exist. An argument goes as follows. Suppose an algorithm exists that sorts your list in $O(n)$ time, then the same algorithm can be used to sort any list in $O(n)$ time as follows. Given ...
Lisa E.'s user avatar
  • 369
3 votes

Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

O(1) means: You need to do this with a fixed number of operations. Basically, write code without a loop. That's not difficult. It's a lot of code, but a fixed amount of code. Look at your heap as if ...
gnasher729's user avatar
  • 30.5k
3 votes
Accepted

How to solve this summation of ceiling function in BUILD-MAX-HEAP algorithm

$$ \begin{align*} \sum_{h=0}^{\lfloor\lg n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h) &< \sum_{h=0}^{\lfloor\lg n\rfloor} \left(1+ \frac{n}{2^{h+1}}\right) O(h) \\ &< \sum_{...
Steven's user avatar
  • 29.5k
3 votes

is AVL tree is better than heap for sorting purpose?

Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data ...
Steven's user avatar
  • 29.5k
3 votes

Worst case time complexity of heap sort

An algorithm can have worst-case running time that is both $O(n \lg n)$ and $\Omega(n \lg n)$; those don't contradict each other. See How does one know which notation of time complexity analysis to ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

Are comparison sort algos appropriate for SUBJECTIVE sorting?

I suggest reading about the theory on rating systems and ranking systems. There are many standard algorithms and methods for this. I would recommend reading the following resources, to get you ...
D.W.'s user avatar
  • 161k
2 votes

Worst case time complexity of heap sort

Note $$\log (n-1)!\ge \log \frac{n-1}{2}+\cdots+\log (n-1)\ge\frac{n-1}{2}\log \frac{n-1}{2}=\Theta(n\log n).$$
xskxzr's user avatar
  • 7,455
2 votes
Accepted

Please provide me a solution of Max-Heapify using Recursion Tree

Try to solve the recurrent by expanding equality case: $$T(n) = T(2n/3) + \Theta(1) = T(2^2n/3^3) + \Theta(1) + \Theta(1)$$ Now you can see $T(n) = \Theta(\log_{\frac{3}{2}}(n))$. Because each time $...
OmG's user avatar
  • 3,572
2 votes
Accepted

How to derive the worst case time complexity of Heapify algorithm?

It's a variable substitution. First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when $i = k$, $k-i = 0$). So, the range of the first summation can be ...
yemre's user avatar
  • 181
2 votes
Accepted

prove that in binary heap buildheap function does at most 2N-2 comparison

Floyd's method of constructing a heap consists of applying heapify on all non-leaf nodes. Running heapify on a node $v$ costs twice the height of the subtree rooted at $v$ (where the height of a leaf ...
Yuval Filmus's user avatar
2 votes
Accepted

Running time of heap sort, when all number are identical

It would be $O(n)$, because each call to a siftdown or siftup procedure would be executed in $O(1)$ if well implemented. Indeed, ...
Nathaniel's user avatar
  • 15.8k
1 vote

Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

Edit: This proof is insufficient as pointed out in comment. I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of ...
Nathaniel's user avatar
  • 15.8k
1 vote

Is it possible to sort this type of array in O(n) time?

no. the easiest proof is a counting argument of how many such lists of size n there are. there's over (n/2)! (since the last half of the elements can be in any order) such lists which implies a time ...
Oscar Smith's user avatar
1 vote
Accepted

Time complexity to remove an item from the heap

Yes, that is correct. O(n) to find an arbitrary item, O(log n) to remove it, total O(n). If you often remove arbitrary items, say you insert n items, then remove the largest or a random item each n/2 ...
gnasher729's user avatar
  • 30.5k
1 vote

Idea for Improving Heapsort

It doesn't matter how you pop, either min first, max first, or alternating. It is still $O(\log n)$ for each pop.
Kenneth Kho's user avatar
1 vote

Complexity of sorting $k$-sorted array using QuickSort and HeapSort

The analysis questioned in Problem 3 assumes(?) an implementation closer to ACM Algorithm 64 than to what Sedgewick is getting at (as does "Problem 1"): ...
greybeard's user avatar
  • 1,074
1 vote

How is the reccurence of Max Heapify T(n)= T(2n/3) + $\theta(1)$?

Consider an heap of height $h \ge 1$ having $2^{h-1}$ leaves on its last level. Let $\ell$ (resp. $r$) be the number of vertices in the subtree rooted in the left (resp. right) child of the root. ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

The expression $\lceil \log_2 n \rceil - 1$ for the height of a $n$-element heap is wrong. For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc... In ...
Steven's user avatar
  • 29.5k
1 vote

What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

Try these: Sorted. Reverse sorted. Two sorted halves. One half ascending, one half descending. Sorted with 0.1%, 1%, 10% random changes. Random. All values equal, 99% equal, 50% equal. Two different ...
gnasher729's user avatar
  • 30.5k
1 vote
Accepted

What is the difference in time-complexity for sorting these 2-d arrays?

The algorithm you suggest for $B$ is a comparison-based algorithm with complexity $O(n \log h)$, where $h$ is the maximum number of elements in the heap. Since $h = \Theta(1)$, you have that $B$ can ...
Steven's user avatar
  • 29.5k
1 vote

Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

I am pretty sure that you cannot solve this problem in $O(1)$ time without additional assumptions. You have to scan at least $L-6$ leaves (which already gives you $\Omega(n)$ time complexity), where $...
Vladislav Bezhentsev's user avatar
1 vote

Max heap and array relation

Suppose an array $A$ is a maxheap. Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property. The maxheap property requires a node's value to be ...
Ashwin Ganesan's user avatar
1 vote

is AVL tree is better than heap for sorting purpose?

No it is not. They both have the same running time but the heap is way lighter for a couple of reasons. For the asymptotic running time, note that a heap can be built in linear time meanwhile applying ...
Narek Bojikian's user avatar
1 vote
Accepted

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

So, basically in heap representation, $LEFT(i)$ refers to the index of $i's$ left child. What we want to show is that index $⌊𝑛/2⌋+1$ is a leaf and is not a middleware node which can be proved if we ...
aminrd's user avatar
  • 499
1 vote

Heap sort best case time - $\mathcal O(n)$?

Because the analysis is performed assuming that there is a strict total order on the keys. Therefore if you are sorting, for example, integers on their usual order, the lower bound applies only as ...
quicksort's user avatar
  • 4,272
1 vote

If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

Let $D(i)$ denote the number of descendants of the $i$th node. In a min-heap, all $D(i)$ nodes below node $i$ must have a larger value than node $i$. Hence, the $n-D(i)$ largest values $n-D(i)+1,\...
mo2019's user avatar
  • 379

Only top scored, non community-wiki answers of a minimum length are eligible