堆排序以及实现的优先队列

堆是一个数组，可以被看成一个近似的完全二叉树，树上的每一个节点对应数组的每个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。

堆又分为大根堆和小根堆
大根堆：父节点总是大于其子节点，
小根堆：父节点总是小于其子节点。

一、建堆

这里是将一个数组转换为一个大根堆(也可转成小根堆)的结构

public class Heap {
    final int MAX = 999;// 定义最大容量999
    private int[] heap;
    private int size;
    /**
     * 初始化一个堆
     * 
     * @param a
     */
    public Heap(int a[]) {
        this.heap = new int[MAX];
        for (int i = 0; i < a.length; i++)//将数组的值传给heap
            heap[i + 1] = a[i];// 堆的下标从1开始
        this.size = a.length;
        // 建堆
        for (int i = this.size / 2; i >= 1; i--) //注释在A，一个图就能明白
            max_Heapify(heap, i, size);
    }
    public int[] getHeap() {
        return heap;
    }
    public int getSize() {
        return size;
    }
    public void printHeap(int heap[], int size) {
        for (int i = 1; i <= size; i++)
            System.out.print(heap[i]);
    }
    public int getParent(int i) {// 获取节点i的父节点下标
        return i / 2;
    }
    public int getLeft(int i) {// 左孩子下标
        return 2 * i;
    }
    public int getRight(int i) {// 右孩子下标
        return 2 * i + 1;
    }
    /**
     * 调整堆结构，使得以i为根节点的子树满足堆结构
     * 
     * @param a
     * @param i
     * @param size 堆的大小
     * @return
     */
    public int[] max_Heapify(int a[], int i, int size) {
        int left = getLeft(i);
        int right = getRight(i);
        int largest;
        // 找到i与其两个子节点中最大的，交换
        if (left <= size && a[i] < a[left]) {
            largest = left;
        } else
            largest = i;
        if (right <= size && a[right] > a[largest])
            largest = right;
        if (largest != i) {
            exchange(a, i, largest);
            max_Heapify(a, largest, size);// 递归地调整，直到满足堆结构
        }
        return a;
    }
    /**堆排序
     * 利用最大堆的第一个元素一定是最大的这个特性，每次将最后一个元素与第一个元素交换，然后调整就可以获得最大值，第二大值....
     * @param a
     * @param size
     * @return
     */
    public  int[] heapSort(int a[],int size) {
        for(int i = size;i>=1;i--) {
            exchange(a,1,i);//交换最后一个元素与第一个元素
            size = size-1;
            max_Heapify(a,1,size);//每次都调整根节点
        }
        return a;
    }
    /**
     * 交换两个下标的元素值
     * 
     * @param a
     * @param x
     * @param y
     */
    public void exchange(int a[], int x, int y) {
        int tmp = a[x];
        a[x] = a[y];
        a[y] = tmp;
    }
}

注释Ａ

二、堆排序

思想：利用堆结构的特点，堆顶的元素值最大，所以我们每次都将堆顶的元素与堆底的元素交换，使size-1，然后重新调整堆结构，这时候的调整就不会影响到堆底的那个最大的元素了，直到堆的size=1时，就完成了排序。排序的顺序是从大到小确定元素的位置。

public  int[] heapSort(int a[],int size) {
        for(int i = size;i>=1;i--) {
            exchange(a,1,i);//交换最后一个元素与第一个元素
            size = size-1;
            max_Heapify(a,1,size);//每次都调整根节点
        }
        return a;
    }

三、用堆结构实现优先队列

队列
堆排序是个优秀的算法，但是实际应用中，快速排序的性能一般优于堆排序，尽管如此，堆这一数据结构仍有许多应用——作为高效的优先队列。和堆一样，优先队列也有两种形式，最大优先队列和最小优先队列。这里我关注于如何基于最大堆实现最大优先队列。
实现
Maximum(S)：返回具有最大关键字的元素

public int Maximum(int a[], int size) {
        return a[1];
    }

push:压入元素(上浮的过程)
1.入队操作
优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮操作，如果插入的数是数组中最大数，自然会上浮到堆顶。如“图1 入队操作”所示：

    public void push(int heap[],int key) {
        int size = this.getSize();
        heap[size+1]=key;
        this.setSize(size+1);
        int i = this.getSize();
        while(i>1&&heap[getParent(i)]<heap[i]) {//如果更改后的key值比其父节点要大，就交换两个节点值
            exchange(heap,i,getParent(i));
            i = getParent(i);
        }
    }

pop：去掉并返回最大关键字的元素
2.出队操作
出队操作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉操作。如“图2 出队操作”所示：

    public int pop(int heap[], int size) {
        if (size < 1) {
            System.out.print("heap underflow");
            return -1;
        }
        int max = heap[1];// 获得最大值
        exchange(heap, 1, size);
        this.setSize(this.getSize() - 1);// 堆size-1
        max_Heapify(heap, 1, this.getSize());// 调整堆结构
        return max;
    }