k****n
发帖数: 369 | 1
no
2> The first thing I can think of is to still use siftdown method, the only
benifit is we don't need to do comparison, just use the right child. This
has been O(N), can it be faster? Let's see what is happening in the
heapifying process:
In a BST:
X
X4 | X
X X1 | X X
X X X2 X3 | X X
At first, X3 will swap with X1, then for X4, it will swap with X3 and then
X1.
So because of the feature of BST, an element is always swapped at the right
hand side, and gurantees to be swapped to the bottom. So ... 阅读全帖 |
|
g**********y
发帖数: 14569 | 2 heap to BST, 我只知道个不完美的答案，把heap sort后，依次填回heap结构中，用
successor()。
BST to heap, 有人给出答案：
public void bst2heap(int a[]) {
int n = a.length;
reverseArm(a, 0, n);
for (int i = 1; i < n / 2; i += 2)
reverseArm(a, i, n);
}
private void reverseArm(int a[], int from, int n) {
int to = from;
while (to * 2 + 2 < n)
to = to * 2 + 2;
while (to > from) {
int t = a[to];
a[to] = a[from];
a[from] = t... 阅读全帖 |
|
