淘宝双十一超级红包 》
堆的 shift up
本小节介绍如何向一个最大堆中添加元素，称为 shift up。
假设我们对下面的最大堆新加入一个元素52，放在数组的最后一位，52大于父节点16，此时不满足堆的定义，需要进行调整。
首先交换索引为 5 和 11 数组中数值的位置，也就是 52 和 16 交换位置。
此时 52 依然比父节点索引为 2 的数值 41 大，我们还需要进一步挪位置。
这时比较 52 和 62 的大小，52 已经比父节点小了，不需要再上升了，满足最大堆的定义。我们称这个过程为最大堆的 shift up。
Java 实例代码
源码包下载：Download
src/runoob/heap/HeapShiftUp.java 文件代码：
package runoob.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());
}
}
/**
* 往堆中添加一元素
*/
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());
}
}