堆插入和删除的简单实现 - JAVA

//注意由于数值是从小标为一开始，当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);
}
}
}
}

堆插入和删除的简单实现(二)