堆：Heap

作者: 梦工厂 | 来源:发表于2015-09-14 09:38 被阅读451次

堆Heap
heap (堆)
Heap 堆
堆：Heap
堆 (Heap)
堆（Heap）
堆（heap）
堆 - Heap
堆（heap）
堆-Heap

一：堆的介绍

Heap是一种数据结构具有以下的特点：

1）完全二叉树；
2）heap中存储的值是偏序；
Min-heap: 父节点的值小于或等于子节点的值；

Max-heap: 父节点的值大于或等于子节点的值；

二：堆的操作

堆的存储：
一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
堆的操作：insert
插入一个元素：新元素被加入到heap的末尾，然后更新树以恢复堆的次序。
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。
堆的操作：Removemax
按定义，堆中每次都删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的，如果父结点比这个最小的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
堆的操作：buildHeap 堆化数组
对于叶子节点，不用调整次序，根据满二叉树的性质，叶子节点比内部节点的个数多1.所以i=n/2 -1 ，不用从n开始。

堆排序
堆建好之后堆中第0个数据是堆中最大的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最大的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

class Heap {
public static void sort(int[] a) {
    if (a == null || a.length == 0) {
        return;
    }
    int len = a.length;
    // 构建heap
    for (int i = len / 2 - 1; i >= 0; i--) {
        down(a, i, len);
    }
    // 排序
    while (len > 1) {
        exch(a, 0, len - 1);
        down(a, 0, len - 1);
        len--;
    }
}
// 向下
private static void down(int[] pq, int k, int len) {
    while (2 * k + 1 < len) {
        int j = 2 * k + 1;
        if (j + 1 < len && less(pq, j, j + 1)) {
            j++;
        }
        if (!less(pq, k, j)) {
            break;
        } else {
            exch(pq, k, j);
            k = j;
        }
    }
}
public static void show(int[] a) {
    for (int i = 0; i < a.length; i++) {
        System.out.println(a[i]);
    }
}
private static boolean less(int[] pq, int i, int j) {
    return pq[i] < pq[j];
}
private static void exch(int[] pq, int i, int j) {
    int temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;
    }
}

三：堆的应用

//基于heap的优先级队列，N有点问题
public class MaxPQ {
    private int[] pq;
    private int N = 0;
    public MaxPQ(int size) {
        pq = new int[size];
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    public void insert(int value) {
        if (N == pq.length) {
            resize(N * 2);
        }
        pq[N] = value;
        swim(N);
        N++;
    }
    public int delMax() {
        int max = pq[0];
        exch(0, N - 1);
        N--;
        sink(0);
        if (N > 0 && N == pq.length / 4) {
            resize(pq.length / 2);
        }
        return max;
    }
    // 由下至上的heap有序化
    private void swim(int k) {
        while (k > 0 && less(pq[(k - 1) / 2], pq[k])) {
            exch((k - 1) / 2, k);
            k = (k - 1) / 2;
        }
    }
    // 由上至下的heap有序化
    private void sink(int k) {
        while ((2 * k + 1) < N) {
            // 选择最大的子节点
            int j = 2 * k + 1;
            if (j + 1 < N && less(j, j + 1)) {
                j = j + 1;
            }
            if (!less(k, j)) {
                break;
            } else {
                exch(k, j);
                k = j;
            }
        }
    }
    private void resize(int max) {
        int[] temp = new int[max];
        for (int i = 0; i < N; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }
    private boolean less(int a, int b) {
        return a < b ? true : false;
    }
    private void exch(int i, int j) {
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }
}

@梦工厂