New answers tagged heaps
0
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.
2
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 ...
3
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 ...
0
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
