堆

what ? why ? when ? how ?

why

为什么要用堆？

what

什么是堆？

堆有什么特点？

how

如何操作堆（建立、插入、删除、查找）？

when

---

什么是堆？

堆是特殊的“队列”，从堆中取出元素是按照元素优先级大小，而不是元素进入队列的先后顺序。

堆是一颗完全二叉树，其结点的值大于或小于其子结点的值（大于是最大堆 小于是最小堆）。

最大堆：

最小堆：

为什么要用堆？

堆也被称为“优先队列”。 比如做事情：事情 A 明天需要完成，事情 B 这周需要完成，事情 C 这个月需要完成。 事情 A 、 B 、 C 出现的顺序是 C 早于 B 早于 C ，正常情况下都将 A 置为优先级最高，B 其次，C 最低。虽然事情 C 最先知道要做但是由于优先级（时间紧迫）需要先把事件 A 先完成。

堆有什么特点？

堆的两个特性：

结构性：用数组表示的完全二叉树；

有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)。

如何操作堆（建立、插入、删除、判空、判满）？

最大堆的操作

class Heap {
int[] data; //存储元素
int size;   //堆中当前元素的个数
int capacity;   //堆的最大容量
}

建立

/**
 * 创建堆
 *
 * @param capacity
 * @return
 */
public static Heap createHeap(int capacity) {
    if (capacity <= 0) {
        System.out.println("创建失败：capacity 值为0或负数");
        return null;
    }
    Heap heap = new Heap();
    heap.data = new int[capacity + 1];
    heap.size = 0;
    heap.capacity = capacity;
    return heap;
}

判空

    /**
 * 堆是否为空
 *
 * @param heap
 * @return
 */
public boolean isEmpty(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == 0;
}

判满

    /**
 * 堆中元素是否满了
 *
 * @param heap
 * @return
 */
public boolean isFull(Heap heap) {
    if (heap == null) {
        System.out.println("Heap is null.");
        return false;
    }
    return heap.size == heap.capacity;
}

插入

思路：

插入最后面比较该节点值和其父亲结点值大小，如果比其父亲结点值大换 一直判断到根。

/**
 * 往堆中插入元素
 *
 * @param heap
 * @param element
 * @return
 */
public boolean insert(Heap heap, int element) {
    if (heap == null) {
        System.out.println("Heap is null. 插入失败");
        return false;
    } else if (isFull(heap)) {
        System.out.println("堆满了,插入失败");
        return false;
    }
    int i = 0;
    i = ++heap.size;
    for (; element > heap.data[i / 2] && i > 1; i = i / 2) {
        heap.data[i] = heap.data[i / 2];
    }
    //插入元素
    heap.data[i] = element;
    return true;
}

删除堆中的最大值

思路：
将最后一个节点的值替换根结点值然后判断其子节点的值是否比其大，如果比它大换 一直往下判断到其子节点比其小或到最后。

/**
 * 删除堆中的最大值
 *
 * @param heap
 * @return
 */
public int deleteMax(Heap heap) {
    if (heap.isEmpty(heap)) {
        System.out.println("堆为空");
        return -1;
    }
    //读取堆中的最大元素
    int maxElement = heap.data[1];
    //获取堆中最后一个元素并将当前个数减少1
    int lastElement = heap.data[heap.size--];
    int parent=1,child;
    for (; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child] < heap.data[child + 1]) {
            child++;//指向左右孩子结点较大者
        }
        if (lastElement >= heap.data[child] ){
            //找到合适的位置
            break;
        }else{
            //在往下找调整
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent]=lastElement;
    return maxElement;
}

按层遍历

/**
 * 按层遍历堆
 * @param heap
 */
public void layerTraversal(Heap heap){
    if(heap==null){
        System.out.println("Heap is null");
        return;
    }
    int layer=1,num=1;
    while(num<=heap.size){
        //每层的数量
        int layerNum=(int)(Math.pow(2,layer-1));
        for(int i=0;i<layerNum && num<=heap.size;i++){
            System.out.print("--------"+heap.data[num++]);
        }
        System.out.println();
        layer++;
    }
}

结果

    Heap heap=Heap.createHeap(100);
    int [] data={100,34,67,78,98,55,44};
    for (int i = 0; i < data.length; i++) {
        if(heap.insert(heap,data[i])){
        }else{
            System.out.println("插入失败");
            break;
        }
    }
    heap.layerTraversal(heap);
    System.out.println("MaxElement: "+heap.deleteMax(heap));
    heap.layerTraversal(heap);

最大堆的建立

记得阿里面试的时候问到过自己没有回答好… 现在想起来应该这样回答

方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为 O(NlogN).

方法2：在线性时间复杂度下建立最大堆。
1. 将N个元素按输入顺序存入，先满足完全二叉树的结构特性
2. 调整各结点位置，以满足最大堆的有序特性。

方法2

public void buildMaxHeap(Heap heap, int[] data) {
    if (heap == null) {
        System.out.println("Heap is null");
        return;
    }
    if ((heap.capacity - heap.size) < data.length) {
        System.out.println("堆容量不足");
        return;
    }
    for (int i = 0; i < data.length; i++) {
        heap.data[++size] = data[i];
    }

    for (int i = heap.size / 2; i > 0; i--) {
        percDown(heap, i);
    }
}

//调整
public void percDown(Heap heap, int p) {
    int parent, child;
    int temp = heap.data[p];
    for (parent = p; parent * 2 <= heap.size; parent = child) {
        child = parent * 2;
        if (child != heap.size && heap.data[child+1] > heap.data[child]) {
            //指向左右结点较大者
            child++;
        }
        if (temp > heap.data[child]) {
            break;
        } else {
            heap.data[parent] = heap.data[child];
        }
    }
    heap.data[parent] = temp;
}

证明方法 2 建造最大堆时间复杂度为 O(N)

若二叉树高为 h ，是一棵满二叉树 (堆是一棵完全二叉树结点数一定小于满二叉树)，那么结点的个数是 n=2^h -1

最后一层节点数 2^(h-1) 个， 最后第二层 2^(h-2) 个 …. 第一层 2^(h-h) 个

2^(h-2) 个结点向下访问一次，2^(h-3) 个结点向下访问两次… 1 个结点向下访问 h-1 次。

公式推导：

源代码：https://github.com/rookieLJ/Tree.git

TestHeap.java

总结

参考
数据结构 陈越 何钦铭
https://blog.csdn.net/anonymalias/article/details/8807895

堆是一个“优先队列”。

堆的特点：完全二叉树、每个结点大于或小于其子结点的值。从根结点到任意结点路径上结点序列的有序性。

最大堆的建立（第二种方法），时间复杂度 O(N)。

有什么问题欢迎指出，感谢！