Something like solution 1 is probably better.
heap[i] = k
- If
heap[i]
is smaller than its parent, bubble it up (swim)
- Otherwise, if
heap[i]
is larger than one of its children, bubble it down (sink)
Running time: O(log n)
.
To swim - While it's smaller than its parent, swap it with its parent.
To sink - While it's larger than one of its children, swap it with its smallest child.
Some Java code for sink
and swim
, taken from here:
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…