# Tag Info

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