博客

// 添加一个元素方法
public void pushHeap(int[] heap, int value) {
    // 全局变量，记录堆的大小，添加时+1
    size++;
    // 把新增的元素放在最后
    heap[size - 1] = value;
    if (size == 1) {
        return;
    }
    // 有子节点的最后一个节点
    int loop = size / 2 - 1; 
    int newIndex = size - 1;
    while (loop > 0) {
        int index = loop;
        if (heap[newIndex] > heap[index]) {
            int tmp = heap[index];
            heap[index] = heap[newIndex];
            heap[newIndex] = tmp;
            newIndex = index;
        } else {
            break;
        }
        loop = (index + 1) / 2 - 1;
    }
}

// 推出一个顶端元素
public int pollHeap(int[] heap) {
    // 直接返回顶端元素
    int res = heap[0];
    // 最后一位元素放到顶端
    heap[0] = heap[size - 1];
    int index = 0;
    int left = 1;
    int right = 2;
    // 节点如果比子元素小就循环
    while (heap[index] < (Math.max(heap[left], heap[right]))) {
        int tmp = heap[index];
        // 找到最大的子节点，替代节点的位置
        if (heap[left] > heap[right]) {
            heap[index] = heap[left];
            heap[left] = tmp;
            index = left;
        } else {
            heap[index] = heap[right];
            heap[right] = tmp;
            index = right;
        }
        // 子节点的下标就是原本的下标*2 + 1
        left = index + index + 1;
        right = left + 1;
        if (left > size - 1) {
            break;
        }
    }
    // 把最后一位归0
    heap[size - 1] = 0;
    // 全局变量，记录堆的大小，推出时减1
    size--;
    return res;
}

// 测试用例
public void heap() {
    // 没有做扩容，就给了个不会溢出的值
    int[] heap = new int[20];
    this.pushHeap(heap, 6);
    this.pushHeap(heap, 3);
    this.pushHeap(heap, 4);
    this.pushHeap(heap, 14);
    this.pushHeap(heap, 12);
    this.pushHeap(heap, 24);
    this.pushHeap(heap, 22);
    this.pushHeap(heap, 34);
    this.pushHeap(heap, 2);
    this.pushHeap(heap, 5);
    this.pushHeap(heap, 1);
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
    System.out.println(pollHeap(heap));
}

没有做什么优化，当记个笔记了