堆插入和删除的简单实现

核心提示： import java.util.*;/***实现的堆的插入和删除操作* @author Arthur*/public class Heap {/*** 递归实现* 删除一个堆中一个数据的时候，根据堆的性质，堆插入和删除的简单实现，应该把相应的位置下移，才能保持住堆性质不变* @param a 保持堆元素的数组* @

 import java.util.*;

/**
*实现的堆的插入和删除操作
* @author Arthur
*/
public class Heap {

/**
* 递归实现
* 删除一个堆中一个数据的时候，根据堆的性质，应该把相应的位置下移，才能保持住堆性质不变
* @param a 保持堆元素的数组
* @param index 被删除的那个节点的位置
*/
public static void heapDown(List heap, int index) {
//因为第一个位置存储的是空值，不在考虑之内
int n = heap.size() - 2;

//记录最小的那个儿子节点的位置
int child = -1;

//2*index>n说明该节点没有左右儿子节点了，那么就返回
if (2 * index > n) {
return;
} //如果左右儿子都存在
else if (2 * index < n) {

//定义左儿子节点
child = 2 * index;
//如果左儿子大于右儿子的数值，取右儿子的下标
if ((Integer) heap.get(child) > (Integer) heap.get(child + 1)) {
child++;
}

}//如果只有一个儿子（左儿子节点）
else if (2 * index == n) {
child = 2 * index;
}

if ((Integer) heap.get(child) < (Integer) heap.get(index)) {
//交换堆中的child，和index位置的值
swap(heap, child, index);

//完成交换后递归调用，继续下降
heapDown(heap, child);
}
}

//非递归实现
public static void heapDown2(List heap, int index) {
int child = 0;//存储左儿子的位置

int temp = (Integer) heap.get(index);
int n = heap.size() - 2;
//如果有儿子的话
for (; 2 * index <= n; index = child) {
//获取左儿子的位置
child = 2 * index;
//如果只有左儿子
if (child == n) {
child = 2 * index;
} //如果右儿子比左儿子的数值小
else if ((Integer) heap.get(child) > (Integer) heap.get(child + 1)) {
child++;
}

//如果数值最小的儿子比temp的值小
if ((Integer) heap.get(child) < temp) {
//交换堆中的child，和index位置的值
swap(heap, child, index);
} else {
break;
}
}
}

/**
* 删除堆中最小的值，也就是删除位置是1的值，也就是根节点的值
* 操作原理是：当删除根节点的数值时，原来的位置就会出现一个孔
* 填充这个孔的方法就是，把最后的叶子的值赋给该孔，最后把该叶子删除
* @param heap
*/
public static void deleteMin(List heap) {
//把最后的一个叶子的数值赋值给1个位置
heap.set(1, heap.get(heap.size() - 1));
//下滤操作
heapDown2(heap, 1);
// heapDown(heap, 1);
//把最后一个位置的数字删除
heap.remove(heap.size() - 1);
}

public static void main(String args[]) {
List array = new ArrayList(Arrays.asList(null, 1, 2, 5, 10, 3, 7, 11, 15, 17, 20, 9, 15, 8, 16));
//deleteMin(array);结果是2 3 5 10 9 7 11 15 17 20 16 15 8
insert(array, 0);//结果是0 2 1 10 3 7 5 15 17 20 9 15 8 16 11
print(array);
}
//打印链表
public static void print(List list) {
for (int i = 1; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}

//把堆中中的a,b位置的值互换
public static void swap(List heap, int a, int b) {
//临时存储child位置的值
int temp = (Integer) heap.get(a);

//把index的值赋给child的位置