堆插入和删除的简单实现

核心提示：heap.set(a, heap.get(b));//把原来的child位置的数值赋值给index位置heap.set(b, temp);}//向堆中插入元素public static void insert(List heap, int value) {heap.add(value);//开始上升操作heapUp2(

heap.set(a, heap.get(b));

//把原来的child位置的数值赋值给index位置
heap.set(b, temp);
}

//向堆中插入元素
public static void insert(List heap, int value) {
heap.add(value);
//开始上升操作
heapUp2(heap, heap.size() - 1);
// heapUp(heap, heap.size() - 1);

}

//上升，让插入的数和父节点的数值比较，当大于父节点的时候就和节点的值相交换
public static void heapUp(List heap, int index) {

//注意由于数值是从小标为一开始，当index = 1的时候，已经是根节点了
if (index > 1) {
//保存父亲的节点
int parent = index / 2;

//获取相应位置的数值
int parentValue = (Integer) heap.get(parent);
int indexValue = (Integer) heap.get(index);
//如果父亲节点比index的数值大，就交换二者的数值
if (parentValue > indexValue) {
//交换数值
swap(heap, parent, index);
//递归调用
heapUp(heap, parent);
}

}
}

//非递归实现
public static void heapUp2(List heap, int index) {
int parent = 0;
for (; index > 1; index /= 2) {
//获取index的父节点的下标
parent = index / 2;

//获得父节点的值
int parentValue = (Integer) heap.get(parent);
//获得index位置的值
int indexValue = (Integer) heap.get(index);

//如果大于就交换
if (parentValue > indexValue) {
swap(heap, parent, index);
}
}
}
}