堆的 shift up

精华

小牛编辑

150浏览

2023-03-14

本小节介绍如何向一个最大堆中添加元素，称为 shift up。

假设我们对下面的最大堆新加入一个元素52，放在数组的最后一位，52大于父节点16，此时不满足堆的定义，需要进行调整。

首先交换索引为 5 和 11 数组中数值的位置，也就是 52 和 16 交换位置。

此时 52 依然比父节点索引为 2 的数值 41 大，我们还需要进一步挪位置。

这时比较 52 和 62 的大小，52 已经比父节点小了，不需要再上升了，满足最大堆的定义。我们称这个过程为最大堆的 shift up。

Java 实例代码

src/heap/HeapShiftUp.java 文件代码：

package heap ;

/**
* 往堆中添加一元素
*/
public class HeapShiftUp <T extends Comparable > {

protected T [ ] data ;
protected int count ;
protected int capacity ;

// 构造函数, 构造一个空堆, 可容纳capacity个元素
public HeapShiftUp ( int capacity ) {
data = (T [ ] ) new Comparable [capacity + 1 ] ;
count = 0 ;
this. capacity = capacity ;
}
// 返回堆中的元素个数
public int size ( ) {
return count ;
}

// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty ( ) {
return count == 0 ;
}
// 像最大堆中插入一个新的元素 item
public void insert (T item ) {
assert count + 1 <= capacity ;
data [count + 1 ] = item ;
count ++;
shiftUp (count ) ;
}
// 交换堆中索引为i和j的两个元素
private void swap ( int i, int j ) {
T t = data [i ] ;
data [i ] = data [j ] ;
data [j ] = t ;
}

//********************
//* 最大堆核心辅助函数
//********************
private void shiftUp ( int k ) {

while ( k > 1 && data [k / 2 ]. compareTo (data [k ] ) < 0 ) {
swap (k, k / 2 ) ;
k /= 2 ;
}
}

// 测试 HeapShiftUp
public static void main ( String [ ] args ) {
HeapShiftUp <Integer > heapShiftUp = new HeapShiftUp <Integer > ( 100 ) ;
int N = 50 ; // 堆中元素个数
int M = 100 ; // 堆中元素取值范围[0, M)
for ( int i = 0 ; i < N ; i ++ )
heapShiftUp. insert ( new Integer ( ( int ) ( Math. random ( ) * M ) ) ) ;
System. out. println (heapShiftUp. size ( ) ) ;

}
}