Heap 堆

这里的堆不是java中内存分配的堆。只是一种数据结构。

堆是二叉满树，满足条件：父节点的键值大于两个子节点的键值，这不同于二叉搜索树（见Tree），堆对于实现优先级队列是一种好的方式，相对于利用数组的优先级队列 ，利用链表的优先级队列 来说，其插入与删除的效率都是O(log n)

此堆的实现使选择数组作为内部数据结构，使得此堆能容纳的数据有限，但找到最下一层的作右子节点比交方便。用数组存储树时，求当前节点的父节点和左右子节点的公式如下：假设当前节点坐标为x：

父节点：(x-1)/2

左子节点：2 * x + 1

右子节点：2 * x + 2

API如下：

    Heap：构造并指定需要的空间大小

    add：添加数据

    remove：删除最大的数据

    isEmpty：堆是否为空

    其余的都是辅助方法，其中最有用的是：

    trickleDown：将指定位置的节点，按照堆的约定规则向下调整到合适的位置

    trickleUp：将指定位置的节点，按照堆的约定规则向上调整到合适的位置

    print:测试辅助方法

Node为辅助类，表示要存取的键值与数值。

Heap.main：提供简短的测试。

class Node {//表示装数据的节点
    private int key; //排序的关键字
    private Object value;	//数据
    Node(int key, Object value) {
        this.key =  key;
        this.value = value;
    }
    int key() { return key; }
    Object value() { return value; }
}

class Heap {
    private Node[] array;	//序排序的数组
    private int pos;	//当前有效数据的个数
    Heap(int size) {
        array = new Node[size];
    }
   
    void add(Node node) {	//将新数据插入数组
        assert pos < array.length;
        array[pos] = node;	//将新数据插入数组的最后（堆的最后一个元素之后）
        trickleUp(pos++);	//将数据提升致恰当的位置
    }

    Node remove() {	//删除堆的顶
        Node result = array[0];	//将最后一个元素提至堆定
        array[0] = array[--pos];	//将堆顶下降为恰当位置
        trickleDown(0);
        return result;
    }

    boolean isEmpty() {
        return pos == 0;
    }

    private void trickleUp(int index) {
        Node bottom = array[index];		//暂存要提升的数据
        int parent = getParent(index);	//得到父节点的位置
        //如果节点存在，且父节点的关键字的值小于要提升数据的关键字
        while (index > 0 && array[parent].key() < bottom.key()) {
            array[index] = array[parent];	//将父节点下降，留出空位
            index = parent;	//重复以上过程
            parent = getParent(index);
        }
        array[index] = bottom;	//将暂存的数据放入恰当的位置
    }

    private void trickleDown(int index) {
        Node top = array[index];	//存放要下降的数据
        int left = getLeft(index);	//得到左子的位置
        int right = getRight(index);	//得到右子的位置
        int current;	//当前可能要下降的位置

        if(left < pos && right < pos)	//左右子节点有效，当前的位置设置为左右子节点中小的那个
            current = array[left].key() > array[right].key() ? left : right;	
        else if (left < pos) current = left;	//如果左子节点有效，则当前位置设置为左子节点
        else current = -1;	//没有可以下降的位置
        while(current != -1 && array[current].key() > top.key()) {	/当前节点有效且大于要下降的数据
            array[index] = array[current];	//将当前节点向上提升，留出空位
            index = current;	//重复以上过程
            left = getLeft(index);
            right = getRight(index);
            if(left < pos && right < pos)
                current = array[left].key() > array[right].key() ? left : right;
            else if (left < pos) current = left;
            else current = -1;
        }
        array[index] = top;	//将暂存的数据放入恰当的位置
    }

    private int getParent(int index) {
        return (index-1)/2;
    }

    private int getLeft(int index) {
        return 2 * index + 1;
    }

    private int getRight(int index) {
        return 2 * index + 2;
    }

    void print() {
        for(int i=0; i<pos; i++) {
            System.out.print(array[i].key() + ",");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Heap heap = new Heap(100);
        heap.add(new Node(50,"hello"));
        heap.add(new Node(20,"jason"));
        heap.add(new Node(60,"peter"));
        heap.add(new Node(50,"orange"));
        heap.add(new Node(30,"temp"));
        heap.add(new Node(40,"hello"));
        heap.add(new Node(90,"jason"));
        heap.add(new Node(10,"peter"));
        heap.add(new Node(5,"orange"));
        heap.add(new Node(300,"temp"));
        heap.print();
        while(!heap.isEmpty()) {
            Node node = heap.remove();
            System.out.println(node.key() + " = " + node.value());
        }
    }
}