数据结构--堆排序
堆排序
简单来说：堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法
- 最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子
- 那么处于最大堆的根节点的元素一定是这个堆中的最大值
-
这里我们讨论最大堆：当前每个父节点都大于子节点
完全二叉树有个特性：
左边子节点位置 = 当前父节点的两倍 + 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();
}
}
}
查看5道真题和解析
