堆排序

简单来说：堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法

最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子那么处于最大堆的根节点的元素一定是这个堆中的最大值

这里我们讨论最大堆：当前每个父节点都大于子节点

完全二叉树有个特性：左边子节点位置 = 当前父节点的两倍 + 1，右边子节点位置 = 当前父节点的两倍 + 2

不断的进行大顶堆转换

主函数

public static void main(String[] args) { int[] arr = {1,0,6,7,2,3,4}; //定义一个数组 int startIndex = (arr.length-1)/2; //定义开始调整的位置 for(int i =startIndex;i>=0;i--){ ToMaxHeap(arr,arr.length,i); //调整成大顶堆的方法 } System.out.println(Arrays.toString(arr)); //经过上面的操作后，已经把数组变成一个大顶堆，把根元素和最后一个元素进行调换 for(int i = arr.length-1;i>0;i--){ int t = arr[0]; arr[0] = arr[i]; arr[i] = t; //进行调换 ToMaxHeap(arr,i,0); //换完之后我们再把剩余元素换成大顶堆 } }

递归+堆排序

/** * @Author liuhaidong * @Description * @param //arr要排序的数组 size调整元素的个数 index从哪里开始调整 * @Date 19:38 2019/10/2 0002 */ private static void ToMaxHeap(int[] arr, int size, int index) { int leftNodeIndex = index*2 +1; int rightNodeIndex = index*2+2; //获取左右字节的索引 int maxIndx = index; if(leftNodeIndex<size && arr[leftNodeIndex] > arr[maxIndx]){ maxIndx = leftNodeIndex; } if(rightNodeIndex<size && arr[rightNodeIndex] > arr[maxIndx]){ maxIndx = rightNodeIndex; } //查找最大节点所对应的索引 if(maxIndx != index){ int t = arr[maxIndx]; arr[maxIndx] = arr[index]; arr[index] = t; //调换完成后，可能会影响到下面的子树，不是大顶堆，我们还需要再次调整 ToMaxHeap(arr, size, maxIndx); }

PriorityQueue简介

1.PriorityQueue默认为小顶堆，底层数据结构是数组，其中数组是无序的，只有将PriorityQueue中元素依次取出后才是有序的，其常见方法如下

添加元素：add，offer

移除元素：remove，poll，移除队列中最前面的元素，并返回该元素，其中remove(Object o)可以移除队列中指定元素，成功返回true，失败返回false

返回元素：element，peek，返回队列中最前面的元素

注意：以上方法中，前者如果执行失败，则会抛出异常，后者执行失败，返回null(其中offer返回false)

找到指定元素下标：indexOf(Object o)

是否包含指定元素：contains(Object o)

判断队列是否为空：isEmpty()

PriorityQueue()           使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。 PriorityQueue(int initialCapacity)           使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。 PriorityQueue(int initialCapacity, Comparator<? super E> comparator)           使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。

 

2.由于PriorityQueue默认是小顶堆实现，这里想要改成大顶堆的话，只需要输入一个自定义比较器参数即可

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(k, new Comparator<Integer>(){ @Override public int compare(Integer o1, Integer o2){ return 02.compareTo(o1); //或者 o2 - o1 } })

PriorityQueue对元素采用的是堆排序，头是按指定排序方式的最小元素。堆排序只能保证根是最大（最小），整个堆并不是有序的。 方法iterator()中提供的迭代器可能只是对整个数组的依次遍历。也就只能保证数组的第一个元素是最小的。

3Comparator排序原理

Comparator排序实际上就是二叉树排序：使用第一个元素作为根节点，如果之后的元素比第一个小，则放到左子树，否则放到右子树，之后按中序遍历。

实现堆

public class Test3 { /** * 大顶堆 * * @param <T> 参数化类型 */ private final static class MaxHeap<T extends Comparable<T>> { // 堆中元素存放的集合 private List<T> items; // 用于计数 private int cursor; /** * 构造一个椎，始大小是32 */ public MaxHeap() { this(32); } /** * 造诣一个指定初始大小的堆 * * @param size 初始大小 */ public MaxHeap(int size) { items = new ArrayList<>(size); cursor = -1; } /** * 向上调整堆 * * @param index 被上移元素的起始位置 */ public void siftUp(int index) { T intent = items.get(index); // 获取开始调整的元素对象 while (index > 0) { // 如果不是根元素 int parentIndex = (index - 1) / 2; // 找父元素对象的位置 T parent = items.get(parentIndex); // 获取父元素对象 if (intent.compareTo(parent) > 0) { //上移的条件，子节点比父节点大 items.set(index, parent); // 将父节点向下放 index = parentIndex; // 记录父节点下放的位置 } else { // 子节点不比父节点大，说明父子路径已经按从大到小排好顺序了，不需要调整了 break; } } // index此时记录是的最后一个被下放的父节点的位置（也可能是自身），所以将最开始的调整的元素值放入index位置即可 items.set(index, intent); } /** * 向下调整堆 * * @param index 被下移的元素的起始位置 */ public void siftDown(int index) { T intent = items.get(index); // 获取开始调整的元素对象 int leftIndex = 2 * index + 1; // // 获取开始调整的元素对象的左子结点的元素位置 while (leftIndex < items.size()) { // 如果有左子结点 T maxChild = items.get(leftIndex); // 取左子结点的元素对象，并且假定其为两个子结点中最大的 int maxIndex = leftIndex; // 两个子节点中最大节点元素的位置，假定开始时为左子结点的位置 int rightIndex = leftIndex + 1; // 获取右子结点的位置 if (rightIndex < items.size()) { // 如果有右子结点 T rightChild = items.get(rightIndex); // 获取右子结点的元素对象 if (rightChild.compareTo(maxChild) > 0) { // 找出两个子节点中的最大子结点 maxChild = rightChild; maxIndex = rightIndex; } } // 如果最大子节点比父节点大，则需要向下调整 if (maxChild.compareTo(intent) > 0) { items.set(index, maxChild); // 将子节点向上移 index = maxIndex; // 记录上移节点的位置 leftIndex = index * 2 + 1; // 找到上移节点的左子节点的位置 } else { // 最大子节点不比父节点大，说明父子路径已经按从大到小排好顺序了，不需要调整了 break; } } // index此时记录是的最后一个被上移的子节点的位置（也可能是自身），所以将最开始的调整的元素值放入index位置即可 items.set(index, intent); } /** * 向堆中添加一个元素 * * @param item 等待添加的元素 */ public void add(T item) { items.add(item); // 将元素添加到最后 siftUp(items.size() - 1); // 循环上移，以完成重构 } /** * 删除堆顶元素 * * @return 堆顶部的元素 */ public T deleteTop() { if (items.isEmpty()) { // 如果堆已经为空，就报出异常 throw new RuntimeException("The heap is empty."); } T maxItem = items.get(0); // 获取堆顶元素 T lastItem = items.remove(items.size() - 1); // 删除最后一个元素 if (items.isEmpty()) { // 删除元素后，如果堆为空的情况，说明删除的元素也是堆顶元素 return lastItem; } items.set(0, lastItem); // 将删除的元素放入堆顶 siftDown(0); // 自上向下调整堆 return maxItem; // 返回堆顶元素 } /** * 获取下一个元素 * * @return 下一个元素对象 */ public T next() { if (cursor >= items.size()) { throw new RuntimeException("No more element"); } return items.get(cursor); } /** * 判断堆中是否还有下一个元素 * * @return true堆中还有下一个元素，false堆中无下五元素 */ public boolean hasNext() { cursor++; return cursor < items.size(); } /** * 获取堆中的第一个元素 * * @return 堆中的第一个元素 */ public T first() { if (items.size() == 0) { throw new RuntimeException("The heap is empty."); } return items.get(0); } /** * 判断堆是否为空 * * @return true是，false否 */ public boolean isEmpty() { return items.isEmpty(); } /** * 获取堆的大小 * * @return 堆的大小 */ public int size() { return items.size(); } /** * 清空堆 */ public void clear() { items.clear(); } @Override public String toString() { return items.toString(); } } }