- //向最大堆中插入元素, heap:存放堆元素的数组
- public static void insert(List<Integer> heap, int value) {
- //在数组的尾部添加
- if(heap.size()==0)
- heap.add(0);//数组下标为0的位置不放元素
- heap.add(value);
- //开始上升操作
- // heapUp2(heap, heap.size() - 1);
- heapUp(heap, heap.size() - 1);
-
- }
-
- //上升,让插入的数和父节点的数值比较,当大于父节点的时候就和父节点的值相交换
- public static void heapUp(List<Integer> heap, int index) {
-
- //注意由于数值是从下标为1开始,当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);
- }
-
- }
- }
复制代码
代码就是这样了看不懂没关系,数据结构可以不用学那么深。java中用到比较少。 |