# Tag Info

6

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 specific question, Example of a 500-node worst-case array for Heapsort, created by my Java program, is included in Appendix A.3 page 110.

4

HeapSort: A procedure which sorts an array in place. Can be in-place or not in-place, the point is it's using a heap data structure to help sort. Building heap is linear with a careful analysis See more here

4

The paper: The Analysis of Heapsort by Schaffer and Sedgewick shows that Theorem 1: Heapsort requires that at least $\frac{1}{2} n \lg n - O(n)$ data moves for any heap composed of distinct keys. and that Theorem 3: The average number of data moves required to Heapsort a random permutation of $n$ distinct keys is $\sim n \lg n$. It also mentions ...

3

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 it was a binary tree. You want the 7th largest item in your tree. That's the sixth largest of the subtrees L and R. If the item at L is smaller than the item ...

3

\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_{h=0}^{\lfloor\lg n\rfloor} \left(\frac{n}{2^h} + \frac{n}{2^h}\right) O(h) = 2n \sum_{h=0}^{\lfloor\lg n\rfloor} \frac{ O(h) }{2^h} = O\left(n \sum_{h=0}^{\... 3 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 structure). It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, ... 3 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 use? and https://cs.stackexchange.com/a/201/755 for some background that might help understand why that is so. 3 keep in mind, that a heap has a height of O(\log n) and its root contains the minimal element. how long does it take to restore the heap if you remove the root element (the minimum!) and how often you have to do this in order to achieve a sorted list? after that, think of the time you need for building a heap out of n elements in abitrary order 2 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).$$2 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 $\Theta(1)$ is added up to reach to the leaf of the expnasion tree. Also, you can reach this result using the master theorem.

1

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 general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log_2 2^i \rceil - 1 = i-1$. The equality $\lceil \log_2n \rceil -1=\lfloor \... 1 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 be sorted in time$O(n)$. Regarding$A$, the lower bound of$\Omega(m \log m)$on any comparison-based algorithm that sorts$m$elements still applies. Indeed, ... 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$L$is a total number of leaves in a heap, to find an answer. Indeed, suppose that you have an algorithm which solves the problem and scans less than$L-6$... 1 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$n$operations of extract min takes a total of$O(n \log n)$. On the other hand, constructing an AVL tree requires$O(n\log n)$operations meanwhile traversing ... 1 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 could show the index of the left child is larger than the number of elements in the heap. On the other hand,$LEFT(⌊𝑛/2⌋+1) = 2(⌊𝑛/2⌋+1) = 2⌊𝑛/2⌋+2 $and ... 1 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 started and to give you an entry-point and overview and let you figure out which might be best-suited for your particular situation: The Bradley-Terry model ... 1 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 long as each key is different. If you allow the order to not be strict then the analysis is not particularly interesting, your example is indeed a best case. ... 1 Big O is for measuring the worst case time complexity, and in this case it is$O(n)$. The best case is written as$\Omega$. Here is a paper describing the reasoning for the best case. We generally do not consider the case of having only identical elements in the list. 1 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,\ldots,n$cannot be put in node$i$. It turns out that$n-D(i)$can be put in node$i$, and so the maximum possible value for node$i$is$n-D(i)\$. To see how ...

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