# Tag Info

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 ...
• 9,561
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 ...
• 369

### 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 ...
• 30.5k
Accepted

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 ...
• 1,258
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 ...
• 4,474
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 ...
• 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 ...
• 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,\...
• 379

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