Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged


doubly linked list can be sorted by heapsort with O(nlogn) time, O(1) space complexity, but not singly linked-list. merge sort can apply to singly linked list with O(nlogn) time, O(n) space complexity.


When $n = 2^h-1$, the heap is just a complete binary tree of height $h$. Clearly $C_0 = C_1 = 1$. For $h > 1$, we can decompose the heap as follows: The root must be 1. Each of the two children are heaps of size $2^{h-1}-1$ on their respective values. The $2^h-2$ values other than the root can be divided arbitrarily to the two children (each gets exactly ...


The definition you give looks like the definition of a complete tree. With the restriction that nodes are in $[\![1, 2^h-1]\!]$, then it is also a perfect tree of height $h$. Instead of looking at the leaves, you should look at the root of the tree: since the tree is perfect, it has two children of size $2^{h-1}-1$ (this is how $C_{h-1}$ appears). You just ...


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 ...

Top 50 recent answers are included