优先队列与堆排序

本文主要是介绍优先队列与堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PriorityQueue

优先级队列中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。无论何时调用remove方法，总会获得当前优先级队列中的最小元素（其实是返回堆顶元素），但并不是对所有元素都排序。它是采用了堆（一个可以自我调整的二叉树），执行增加删除操作后，可以让最小元素移动到根。

堆排序复习

package com.jefflee;import java.util.Arrays;public class HeapSort {private int[] arr;public HeapSort(int[] arr) {this.arr = arr;}/*** 堆排序*/public void sort(){/**第一步 将数组堆化*beginIndex 是 第一个非叶节点* 从第一个非页节点开始调整* 叶子节点可以看作已符合要求，因为调整的结果是自己比自己的子节点都大*/int len = arr.length - 1;int beginIndex = (len - 1) >> 1;for (int i = beginIndex; i >= 0; i--) {maxHeap(i, len);}/**第2步 用堆排序* 将堆顶跟最后面的节点调换* 调整除了最大元素之外的所有元素（第二个参数--）* 直至len没了*/for (int i = len; i > 0; i--) {swap(0,i);maxHeap(0, i - 1);}}private void swap(int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/***调整大根堆中的i，使其符合大根堆的特性* @param i 针对的索引* @param len 需要调整的范围*/private void maxHeap(int i, int len) {//左右子节点int li = (i << 1) + 1;int ri = li +1;//子节点中的较大者，默认为liint cMax = li;//左子节点不存在，说明i是叶子节点，已满足条件if (li > len) {return;}//比较左右子节点，得到真正的cMaxif (ri <= len && arr[ri] > arr[li]) {cMax = ri;}//若子节点中较大者大于父节点，调换if (arr[cMax] > arr[i]) {swap(cMax, i);//继续调整cMaxmaxHeap(cMax, len);}}public static void main(String[] args) {int[] arr = {1, 4, 1, 6, 2, 3};new HeapSort(arr).sort();//直接printarr是一个object ref，Arrays.toString写了这个工具System.out.println(Arrays.toString(arr));}
}

这篇关于优先队列与堆排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---