数据结构之堆相关

一、堆的定义

堆是计算机学科中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象

堆的特性：

• 它是完全二叉树
• 通常使用数组实现
• 如果一个结点位置为K，则它的父节点位置为K/2，子节点的位置为2K和2K+1
• 每个结点都大于它的子节点，但是两个子节点大小无要求
  

二、手搓堆

package HeapTest;

public class HeapPracticeTest<T extends Comparable<T>> {
    //存储堆中元素
    private T[] items;
    //记录堆中元素的个数
    private int N;
    //初始化一个堆
    public HeapPracticeTest(int capacity){
        items = (T[]) new Comparable[capacity+1];
        N = 0;
    }
    public void insert(T t){
        items[++N] = t;
        //判断插入元素是否破坏堆的有序顺序
        swim(N);
    }
    //上浮算法，插入结点时使用
    private void swim(int n){
        while (n>1){
            //新放入结点大于其父节点则破坏原堆的有序状态，
            // 需要将该结点与其父结点交换位置
            if(items[n].compareTo(items[n/2])>0){
                T temp = items[n];
                items[n] = items[n/2];
                items[n/2] = temp;
            }//待优化部位 如果已经有序是否可以提前结束循环else{break;}
            ////判断交换后结点是否仍大于其父结点
            n = n/2;
        }
    }
    //删除堆中最大结点，以大根堆为例，最大元素就是堆的跟结点
    //具体方法：
    // 1、将堆的最后一个结点放到根结点
    // 2、删除最后一个结点，堆大小-1
    // 3、利用下沉算法，将堆重新变有序
    public T delMax(){
        T max = items[1];
        items[1] = items[N];
        items[N] = null;
        N--;
        //此时的根结点即为临时根结点，用临时根结点进行下沉，
        // 因为抛弃了0号索引，所以根结点索引为1
        sink(1);
        return max;
    }
    private void sink(int k){
        //如果已经下沉到最底层则不用循环,
        // 2*k<=N就是当前判断节点位置有子结点才进行判断
        while(2*k<=N){
            //用以标记两个子结点中的最大值
            int max;
            //寻找当前结点子结点中的最大值
            //判断当前结点是否存在右子结点，存在的话去判断其中最大值
            if (2*k+1<=N){
                if(items[2*k].compareTo(items[2*k+1])>0){
                    max = 2*k;
                }else{
                    max = 2*k+1;
                }
            }else{
                max = 2*k;
            }
            //判断子结点中的最大值是否大于当前结点
            if(items[k].compareTo(items[max])<0){
                //当前结点小于其子结点 开始下沉 ，交换位置
                T temp = items[max];
                items[max] = items[k];
                items[k] = temp;
            }else{
                break;
            }
            //将k跟随临时根结点的移动而移动
            k = max;
        }
    }

    public static void main(String[] args) {
        HeapPracticeTest<String> heap = new HeapPracticeTest<String>(20);
        heap.insert("A");
        heap.insert("B");
        heap.insert("C");
        heap.insert("D");
        heap.insert("E");
        heap.insert("F");
        heap.insert("G");
        String del;
        while((del=heap.delMax())!=null){
            System.out.print(del+",");
        }
    }
}

三、堆排序

利用堆有序的特性，进行排序

步骤：（升序排序）

• 构造堆
• 得到堆顶元素，此值为大根堆的最大值
• 交换堆顶元素与最后一个元素位置
• 构建除去最后一个元素的新堆
• 重复以上步骤

代码如下：

package HeapTest;

import java.util.Arrays;

public class HeapSortTest<T extends Comparable<T>> {
    //对source数组中的数据从小到大排序
    public static void heapSorted(Comparable[] source){
        //创建一个空数组，用以保存堆数据，为source.length+1因为0号索引弃用
        Comparable[] heap = new Comparable[source.length+1];
        //构造堆
        createHeap(source,heap);
        //定义一个变量记录堆中最大元素的索引，初始为heap.length-1
        int N = heap.length-1;
        //如果堆中只有一个元素则无必要继续下沉
        while (N!=1){
            //交换最大元素与堆中最后一个元素的位置
            Comparable temp = heap[N];
            heap[N] = heap[1];
            heap[1] = temp;
            //交换完毕后最大元素已经到堆的最尾部，
            //从堆中删除最后一个结点即可
            N--;
            //从当前根结点进行下沉操作
            sink(heap,1,N);
        }
        //将排好序的heap数组copy至原数组
        System.arraycopy(heap,1,source,0,heap.length-1);
    }
    //构建堆
    private static void createHeap(Comparable[] source,Comparable[] heap){
        //将source原数组中的数据拷贝到heap数组中，形成一个无序的堆
        //arraycopy方法参数((拷贝原数组),开始拷贝索引,拷贝至数组,接收拷贝索引.拷贝数组长度)
        System.arraycopy(source,0,heap,1,source.length);
        // 对无序堆进行下沉操作，使其变成有序的大根堆，
        // 巧妙方法（从数组长度/2处往前进行下沉操作），因为k结点的子结点为2k或2k+1，
        // 大于(数组长度-1)/2的结点都为叶子结点，小于(数组长度-1)/2的结点为分支节点，
        // 因为0索引被废弃所以为(数组长度-1)/2
        for (int i = (heap.length-1)/2;i>1;i--){
            //此时下沉的目的为构造有序堆，所以堆的大小为整个数组
            sink(heap,i,heap.length-1);
        }
    }
    //下沉算法 使堆重新有序，参数1：下沉堆，参数2：下沉结点的索引，参数3：实际堆的大小
    private static void sink(Comparable[] heap,int target,int range){
        //当前结点的左子结点位于堆内，才进行下沉（排序时使用）
        while(2*target<=range){
            int max;    //记录子结点的最大索引
            //当前结点的右子结点是否位于堆中
            if(2*target+1<=range){
                //如果位于堆中，需要比较两个子结点大小，选取最大者进行交换
                if(heap[2*target].compareTo(heap[2*target+1])<0){
                    //左子节点<右子结点
                    max = 2*target+1;
                }else{
                    max = 2*target;
                }
            }else{  //当前结点的右子结点不位于堆中,最大子结点直接就为左子节点
                max = 2*target;
            }
            //判断当前结点与其最大子结点的大小
            if(heap[target].compareTo(heap[max])>0){
                //当前结点大于其最大子结点，不用下沉，直接跳出循环即可
                break;
            }
            //如果当前结点小于最大子结点的大小，就下沉该结点
            Comparable temp = heap[target];
            heap[target] = heap[max];
            heap[max] = temp;
            //target继续追踪当前结点，判断其是否需要再次下沉
            target = max;
        }
    }

    public static void main(String[] args) {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        heapSorted(arr);
        System.out.println(Arrays.toString(arr));
    }
}