2018-08-05 13:44:44 +0000   |     algorithm data structure heap binary tree   |   Viewed times   |    

最小堆的本质是一棵二叉树

最小堆(Min Heap)本质是一棵二叉树,它承诺每个子节点的值都要大于等于父节点的值(所以它的根节点永远都是堆中最小的数字)。它最大的特性是:

  1. 能在O(logn)时间内返回堆中最小元素(因此得名),并维护好它所承诺的结构。
  2. 能在O(logn)时间内向堆中插入一个新元素,并维护好它承诺的结构。

严格地讲一个表示最小堆的二叉树还必须满足下面两个条件:

  1. 每个节点中的值必须小于它左右两个子节点中的值(如果是Max Heap则反之)
  2. 必须是一棵 完全二叉树 (即:除了最后一层叶节点,其他节点必须是一棵满二叉树,并且最后一层所有节点都连续集中在左边。)

下面这个 不是 一棵完全二叉树, min-heap-not-complete

下面这个 一棵完全二叉树, min-heap-is-complete

getMin()函数向下冒泡

从Min Heap里取出当前最小元素(根元素),需要分两步走:

  1. 先用最末尾元素填充到根元素的空位
  2. 然后新的根元素逐渐和自己的子元素比较(向下冒泡),以摆正自己在堆中的正确位置

图示是一个Max Heap,但不影响理解,原理和Min Heap相同, min-heap-get-min

insert()函数向上冒泡

插入新元素过程正好相反,也要分两步走:

  1. 先将新元素填在最末尾的位置
  2. 然后将新元素逐步和父元素比较(向上冒泡),找到自己在堆中正确的位置

图示也是一个Max Heap,表在意, min-heap-insert

用一个数组表示Min Heap

min-heap-array

有几个关键的细节:

代码

下面是一个最简单的只有getMin()insert()函数的Min Heap。

/**
 * Min Heap
 */
package com.ciaoshen.leetcode.myUtils;
import java.util.*;

public class MinHeap {

    public MinHeap(int size) {
        heap = new int[size+1];
        p = 1;
    }
    /**
     * return min value in heap and update the heap
     * @return min value in heap (current root node)
     */
    public int getMin() {
        int min = heap[1];
        heap[1] = heap[--p];
        minHelper(1);
        return min;
    }
    // bubble-down the pseudo-root
    private void minHelper(int root) {
        int left = root * 2, right = left + 1;
        // 当左右子节点中至少有一个大于父节点时
        if ((left < p && heap[left] < heap[root]) || (right < p && heap[right] < heap[root])) {
            // 优先考虑换左节点,只有当右节点确实比左节点小才考虑换右节点
            if (right < p && heap[left] > heap[right]) {
                swap(root,right);
                minHelper(right);
            } else {
                swap(root,left);
                minHelper(left);
            }
        }
    }
    // insert a new number at the end of array and bubble-up it
    public void insert(int val) {
        int curr = p, parent = p / 2;
        heap[p++] = val;
        // 如果新节点值小于其父节点,冒泡
        while (parent > 0 && heap[curr] < heap[parent]) {
            swap(curr,parent);
            curr = parent;
            parent = curr / 2;
        }
    }
    public boolean isEmpty() {
        return p <= 1;
    }
    public String toString() {
        return Arrays.toString(heap);
    }

    private int[] heap;
    private int p;

    private void swap(int a, int b) {
        int temp = heap[a];
        heap[a] = heap[b];
        heap[b] = temp;
    }
}

参考资料

CMU讲义