数据结构之优先级队列、堆及堆排序

优先级队列是一个抽象数据类型，它提供删除插入、最大(最小)关键字值数据项的方法，其主要目的是对极值提供便利的访问。
优先级队列可以用有序数组来实现，也可以用队列来实现。

堆，是一种树，由其实现优先级队列的插入删除操作的时间复杂度都是O(logN)。
堆是有如下特点的二叉树：
1.是完全二叉树。即，除了树的最后一层节点不是满的，其他的每一层都必须是满的。
2.堆中的每一个节点都满足堆的条件，即每一个节点的关键字的值都大于或等于其子节点的关键字的值，而小于父节点关键字的值。
3.最大数据项总是在根位置上。
4.一般用数组实现。
5.堆不能有序地遍历所有数据，不能找到特定关键字数据项的位置，也不能移除特定关键字的数据项。
6.要插入的数据项总是先放在数组中的第一个空的位置上，然后再向上筛选它至适当的位置。
7.当从根移除一个数据项时，用数组中的最后一个数据项代替他的位置，然后再向下筛选这个节点到适当的位置。
8.可以更改任意数据项的优先级。首先，更改其关键字，如果增加，则向上筛选，减少，则向下筛选。

堆排序，是一种高效的排序过程，其时间复杂度为O(N*logN).将一个待排序数组依次写入到堆中，写入完毕之后，依次去除根元素(最大元素)写入到数组中，即完成了排序。可以使用同一个数组来存放初始无序的数据、正在排序的数据以及排好序的数据，因此，堆排序不需要额外的空间。(N次插入,N次移除)。
也可以对无序数组的N/2个数据项进行trickDown()操作，而不作N次插入，可使堆排序运行速度更快。

下面是用数组实现的堆以及堆排序：

package test;
public class Heap {
    Node2[] heapArray;
    int arraySize;// 数组大小
    int currentSize;// 数组中实有数据的大小
    public Heap(int size) {
        arraySize = size;
        currentSize = 0;
        heapArray = new Node2[arraySize];
    }
    public boolean isEmpty() {
        return currentSize == 0;
    }
    // 插入
    public boolean insert(int key) {
        if (currentSize == arraySize)
            return false;
        Node2 node = new Node2(key);// 创建新节点
        heapArray[currentSize] = node;// 将新节点放在数组末尾
        trickUp(currentSize++);// 将其向上筛选，同时计数加1
        return true;
    }
    /**
     * 节点初始时插入到数组中的空的位置，即最后的位置， 但是如果新插入的节点大于它得到的父节点时，会把堆破坏，
     * 因此，需要向上筛选新节点，直到它在一个大于它的父节点之下，在一个小于它的子节点之上。
     */
    public void trickUp(int index) {
        int parent = (index - 1) / 2;// 父节点的下标
        Node2 bottom = heapArray[index];
        while (index > 0 && heapArray[parent].idata < bottom.idata) {
            heapArray[index] = heapArray[parent];// 向下移动父节点
            index = parent;// 将index上移
            parent = (parent - 1) / 2;// 父节点的下标给予其父节点
        }
        heapArray[index] = bottom;
    }
    // 删除根节点
    public Node2 remove() {
        Node2 root = heapArray[0];
        heapArray[0] = heapArray[--currentSize];
        trickDown(0);// 向下筛选
        return root;
    }
    /**
     * 将根节点删除之后，需要找到一个适合的节点来替换之
     */
    public void trickDown(int index) {
        int largerChild;
        Node2 top = heapArray[index];
        while (index < currentSize / 2) {
            int leftChild = index * 2 + 1;
            int rightChild = leftChild + 1;
            if (rightChild < currentSize
                    && heapArray[leftChild].idata < heapArray[rightChild].idata)
                largerChild = rightChild;
            else
                largerChild = leftChild;
            if (top.idata >= heapArray[largerChild].idata)
                break;
            heapArray[index] = heapArray[largerChild];
            index = largerChild;
        }
        heapArray[index] = top;
    }
    public void show() {
        for (int i = 0; i < currentSize; i++) {
            if (heapArray[i] != null)
                System.out.println(heapArray[i].idata + " ");
            else
                System.out.println("* ");
        }
    }
    public static void main(String[] args) {
        Heap heap = new Heap(6);
        heap.insert(12);
        heap.insert(23);
        heap.insert(4);
        heap.insert(2);
        heap.insert(8);
        heap.show();
        Node2 node = heap.remove();
        System.out.println("the remove node = " + node.idata);
        heap.show();
        // 堆排序
        Item[] item = { new Item(3), new Item(1), new Item(5), new Item(2),
                new Item(7) };
        for (int i = 0; i < item.length; i++)
            heap.insert(item[i].idata);
        for (int i = 0; i < item.length; i++) {
            n = heap.remove();
            item[i].idata = n.idata;
        }
        //打印数组
        for (int i = 0; i < item.length; i++)
            System.out.print(item[i].idata + " . ");
    }
}
class Node2 {
    int idata;
    public Node2(int idata) {
        this.idata = idata;
    }
}