一、堆的模擬實現(xiàn)
1.1堆的概念
如果有一個關鍵碼的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉樹的順序存儲方式存儲 在一個一維數(shù)組中，并滿足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，則稱為 小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。
1.2 堆的性質
堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；
堆總是一棵完全二叉樹。
如下圖就是大根堆和小根堆
1.3堆的存儲結構
從堆的概念可知，堆是一棵完全二叉樹，因此可以層序的規(guī)則采用順序的方式來高效存儲
注意：
- 對于非完全二叉樹，則不適合使用順序方式進行存儲，因為為了能夠還原二叉樹，空間中必須要存儲空節(jié)點，就會導致空間利用率比較低。
- 將元素存儲到數(shù)組中后，可以根據(jù)二叉樹章節(jié)的性質5對樹進行還原。假設i為節(jié)點在數(shù)組中的下標，則有：
如果i為0，則i表示的節(jié)點為根節(jié)點，否則i節(jié)點的雙親節(jié)點為 (i - 1)/2
如果2 * i + 1 小于節(jié)點個數(shù)，則節(jié)點i的左孩子下標為2 * i + 1，否則沒有左孩子
如果2 * i + 2 小于節(jié)點個數(shù)，則節(jié)點i的右孩子下標為2 * i + 2，否則沒有右孩子
1.4堆的創(chuàng)建
要完成堆的創(chuàng)建，首先需要了解幾個完全二叉樹的性質。
- 如果一致完全二叉樹有n個結點，那么最后一個葉子結點的坐標是n-1(根節(jié)點是從0開始的),最后一個父節(jié)點的坐標是(n-1-1)/2
- 如果父節(jié)點的下標是i,那么其左孩子（如果有）的下標是2i+1;右孩子（如果有）的下標是2i+1。
1.4.1 只有根節(jié)點不滿足堆的特性
如上圖，發(fā)現(xiàn)只有根節(jié)點沒有滿足小根堆的特性，那么我們如何將這個堆調整至符合小根堆特性呢？
要知道這些數(shù)據(jù)實際都是用數(shù)組的形式進行存儲的，我們可以通過下標去訪問每個數(shù)據(jù)。
- 我們先用一個parent指向根節(jié)點，那么其左孩子child的下標是(2parent+1)，右孩子的下標是child+1；
- 我們無非是比較三者誰大誰小，選取最小的哪一個（其下標重新賦值為child），將其與父節(jié)點（也就是parent）的值進行交換。
- 但是這樣就會有新的問題，這回導致根節(jié)點的子樹不再滿足小根堆的性質，所以還要繼續(xù)對子樹進行調整，所以我們此時將parent的值賦值為child,指向更改后的子樹的根節(jié)點，在重復上述步驟即可
代碼如下
public void shutDown(int parent,int useSize){
int child = 2*parent+1;//找到左孩子
while(child<useSize){//child<useSize可以作為循環(huán)的終止條件，也可以作為判斷父節(jié)點是否有左孩子的條件
if(child+1<useSize && elem[child]>elem[child+1]) {//child+1<useSize判斷是否有右孩子，
child++;//elem[child]<elem[child+1]結合child++用于取得左右孩子的最小值。
}
//注意：如果不滿足child+1<useSize，也就是所只有左孩子沒有右孩子，那么此時去判斷左孩子值與根節(jié)點誰大誰小，
// 這里千萬不能把if(elem[parent]>elem[child])寫到if(child+1<useSize && elem[child]>elem[child+1])里面去，這樣的話就會有最后一個只有左孩子的父節(jié)點沒有調整的情況
if(elem[parent]>elem[child]){//如果父節(jié)點的值比子節(jié)點最小值要大，那么就要交換
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
//調整好這個父節(jié)點之后有可能會導致子樹不再滿足小根堆的特性，所以要繼續(xù)往下調整
parent = child;
child = 2*parent+1;
}
else{
break;//如果父節(jié)點的值比子節(jié)點最小值要小，那么就不交換，直接break，注意此時是不需要再往下去看子樹是否滿足小根堆的，一定是
//滿足的，因為前面的if里面是從最后的父節(jié)點一路往前調整的，所以后面的一定滿足小根堆的特性
}
}
}
1.4.2 不只有根節(jié)點不滿足堆的特性
其實這種情況是非常好處理的，只需要遍歷一遍父節(jié)點即可，把每個父節(jié)點都當做當前子樹的根節(jié)點去處理即可
1.4.2.1 建堆代碼
所以完整的建立小根堆的代碼如下
public class TestHeap {
public int[] elem;
public int useSize;
public TestHeap(){
this.elem = new int[10];
this.useSize = 0;
}
//初始化一個數(shù)組，將輸入的數(shù)組全部用elem數(shù)組存起來
public void initElem(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
useSize++;
}
}
//創(chuàng)建一個大根堆
public void createShortHeap(){
//從最后一個父節(jié)點開始向下去調整
for (int i = (elem.length-1-1)/2; i >=0 ; i--) {
//elem.length-1表示最后一個結點的下標，最后一個結點下標減一再除以二就是最后一個父節(jié)點的坐標
shutDown(i,useSize);
}
}
//向下調整
public void shutDown(int parent,int useSize){
int child = 2*parent+1;//找到左孩子
while(child<useSize){//child<useSize可以作為循環(huán)的終止條件，也可以作為判斷父節(jié)點是否有左孩子的條件
if(child+1<useSize && elem[child]>elem[child+1]) {//child+1<useSize判斷是否有右孩子，
child++;//elem[child]<elem[child+1]結合child++用于取得左右孩子的最小值。
}
//注意：如果不滿足child+1<useSize，也就是所只有左孩子沒有右孩子，那么此時去判斷左孩子值與根節(jié)點誰大誰小，
// 這里千萬不能把if(elem[parent]>elem[child])寫到if(child+1<useSize && elem[child]>elem[child+1])里面去，這樣的話就會有最后一個只有左孩子的父節(jié)點沒有調整的情況
if(elem[parent]>elem[child]){//如果父節(jié)點的值比子節(jié)點最小值要大，那么就要交換
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
//調整好這個父節(jié)點之后有可能會導致子樹不再滿足小根堆的特性，所以要繼續(xù)往下調整
parent = child;
child = 2*parent+1;
}
else{
break;//如果父節(jié)點的值比子節(jié)點最小值要小，那么就不交換，直接break，注意此時是不需要再往下去看子樹是否滿足小根堆的，一定是
//滿足的，因為前面的if里面是從最后的父節(jié)點一路往前調整的，所以后面的一定滿足小根堆的特性
}
}
}
}
測試代碼
public class Test {
public static void main(String[] args) {
TestHeap testHeap = new TestHeap();
int[] array = {27,15,19,18,28,34,65,49,25,37};
testHeap.initElem(array);
for (int i = 0; i < testHeap.elem.length; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.createShortHeap();
for (int i = 0; i < testHeap.elem.length; i++) {
System.out.print(testHeap.elem[i]+" ");
}
}
}
測試結果
1.4.2.2 建堆過程圖示
如下圖是上面這個例子的建立小根堆的過程
1.4.3 建堆的時間復雜度
我們用滿二叉樹來進行分析，多幾個結點不影響結果，滿二叉樹也方便計算
所以
1.5堆的插入
1.5.1堆的插入的基本思想
首先，堆的插入一定是從堆的末尾開始插入的，不能從中間開始插入
在對末尾插入之后該堆就不一定符合小根堆的特性了，需要向上調整。
如下圖
首先需要知道的是，在完全二叉樹里，如果子節(jié)點的下標是i,那么該子節(jié)點對應的父節(jié)點的下標就是(i-1)/2。
- 我們將插入結點的下標賦值為child,那么其父節(jié)點的下標為parent = (child-1)/2。
- 比較child的值與parent的值誰大誰小，如果child的值比較小，就需要調換child的值與parent的值，反之則不需要調整。
- 在一次調整之后，還需要往上繼續(xù)調整，所以將child = parent;parent = (child-1)/2。
1.5.2堆的插入的完整代碼
//插入
public void offer(int val) {
if (isFull()) {//判斷堆是不是滿了，滿了就調用copyof進行擴容；
elem = Arrays.copyOf(elem, (elem.length) * 2);
}
//在堆的末尾插入
this.elem[useSize] = val;
//重新調整堆為小根堆
shiftUp(useSize);
//一定要注意這三句的順序，最后useSize++
useSize++;
}
//向上調整
public void shiftUp(int child) {//child 就是插入的位置下標
int parent = (child - 1) / 2;
while (parent >= 0) {//注意這里是parent>=0,因為parent = 0時正好是根節(jié)點的情況，這是也是有可能需要調整的。
if (elem[parent] > elem[child]) {//如果子節(jié)點的值比父節(jié)點的值要小，那么就是需要調整的。
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
child = parent;
parent = (child - 1) / 2;
} else {
break;//如果插入的數(shù)（孩子結點）的值比其父節(jié)點的值本來就要大，那么是滿足小根堆特性的，不需要調整。
}
}
}
//判滿
public boolean isFull() {
if (useSize == elem.length) {
return true;
}
return false;
}
測試代碼
public class Test {
public static void main(String[] args) {
TestHeap testHeap = new TestHeap();
int[] array = {27,15,19,18,28,34,65,49,25,37};
testHeap.initElem(array);
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.createShortHeap();
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.offer(10);
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
}
}
測試結果
1.5.3堆的插入的過程圖示
下圖就是上述代碼的執(zhí)行過程
1.6堆的刪除
1.6.1堆的刪除的基本操作
首先堆刪除的元素一定是堆首元素（也就是一定是數(shù)組首元素）
堆的刪除的具體操作
- 將堆頂元素與堆尾元素互換，將堆尾元素刪除（useSize-1）
- 從堆頂開始向下調整，重新調整至符合大根堆（小根堆）。
1.6.2堆的刪除的代碼
經(jīng)過前面的代碼學習，其實刪除已經(jīng)很簡單了
向下調整的代碼我們已經(jīng)寫過了，只需要調用即可
//刪除
public void poll(){
if(!isEmpty()){
elem[0] = elem[useSize-1];//堆尾元素賦值為堆首元素
useSize--;//useSize-1表示刪除最后一個元素
shiftDown(0, useSize);
}
else{
return;
}
}
//判空
public boolean isEmpty(){
if(useSize == 0){
return true;
}
return false;
}
//向下調整
public void shiftDown(int parent, int useSize) {
int child = 2 * parent + 1;//找到左孩子
while (child < useSize) {//child<useSize可以作為循環(huán)的終止條件，也可以作為判斷父節(jié)點是否有左孩子的條件
if (child + 1 < useSize && elem[child] > elem[child + 1]) {//child+1<useSize判斷是否有右孩子，
child++;//elem[child]<elem[child+1]結合child++用于取得左右孩子的最小值。
}
//注意：如果不滿足child+1<useSize，也就是所只有左孩子沒有右孩子，那么此時去判斷左孩子值與根節(jié)點誰大誰小，
// 這里千萬不能把if(elem[parent]>elem[child])寫到if(child+1<useSize && elem[child]>elem[child+1])里面去，這樣的話就會有最后一個只有左孩子的父節(jié)點沒有調整的情況
if (elem[parent] > elem[child]) {//如果父節(jié)點的值比子節(jié)點最小值要大，那么就要交換
int tmp = elem[parent];
elem[parent] = elem[child];
elem[child] = tmp;
//調整好這個父節(jié)點之后有可能會導致子樹不再滿足小根堆的特性，所以要繼續(xù)往下調整
parent = child;
child = 2 * parent + 1;
} else {
break;//如果父節(jié)點的值比子節(jié)點最小值要小，那么就不交換，直接break，注意此時是不需要再往下去看子樹是否滿足小根堆的，一定是
//滿足的，因為前面的if里面是從最后的父節(jié)點一路往前調整的，所以后面的一定滿足小根堆的特性
}
}
}
測試代碼
public class Test {
public static void main(String[] args) {
TestHeap testHeap = new TestHeap();
int[] array = {27,15,19,18,28,34,65,49,25,37};
testHeap.initElem(array);
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.createShortHeap();
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.offer(10);
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
System.out.println();
testHeap.poll();
for (int i = 0; i < testHeap.useSize; i++) {
System.out.print(testHeap.elem[i]+" ");
}
}
}
結果
1.6.3堆的刪除的過程圖示
二、優(yōu)先級隊列
2.1優(yōu)先級隊列的概念
在java中堆和優(yōu)先級隊列是一個概念，前面介紹過隊列，隊列是一種先進先出(FIFO)的數(shù)據(jù)結構，但有些情況下，操作的數(shù)據(jù)可能帶有優(yōu)先級，一般出隊列時，可能需要優(yōu)先級高的元素先出隊列，該中場景下，使用隊列顯然不合適，比如：在手機上玩游戲的時候，如果有來電，那么系統(tǒng)應該優(yōu)先處理打進來的電話；初中那會班主任排座位時可能會讓成績好的同學先挑座位。在這種情況下，數(shù)據(jù)結構應該提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結構就是優(yōu)先級隊列(Priority Queue)（該段引用自比特講義）。
2.2優(yōu)先級隊列的常用接口
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue兩種類型的優(yōu)先級隊列，PriorityQueue是線程不安的，PriorityBlockingQueue是線程安全的。這里我們重點介紹PriorityQueue。
2.3PriorityQueue的特性
關于PriorityQueue的使用要注意：
- 使用時必須導入PriorityQueue，即
import java.util.PriorityQueue; - PriorityQueue中放置的元素必須要能夠比較大小，不能插入無法比較大小的對象，否則會拋出
ClassCastException異常 - 不能插入null對象，否則會拋出
NullPointerException異常 - 沒有容量限制，可以插入任意多個元素，其內部可以自動擴容
- 插入和刪除元素的時間復雜度為O（logN）
- PriorityQueue底層使用了堆數(shù)據(jù)結構
- PriorityQueue默認情況下是小堆—即每次獲取到的元素都是最小的元素
2.4PriorityQueue的構造方法
PriorityQueue()
創(chuàng)建一個PriorityQueue ，具有默認的初始容量（11），根據(jù)它們的natural ordering對其元素進行排序 。
PriorityQueue(Collection<? extends E> c)
創(chuàng)建一個 包含了集合C中的所有元素的PriorityQueue。
PriorityQueue(int initialCapacity)
創(chuàng)建PriorityQueue并指定的初始容量initialCapacity
示例
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.offer(27);
priorityQueue1.offer(15);
priorityQueue1.offer(19);
priorityQueue1.offer(18);
priorityQueue1.offer(28);
priorityQueue1.offer(34);
priorityQueue1.offer(65);
priorityQueue1.offer(49);
priorityQueue1.offer(25);
priorityQueue1.offer(37);
//使用迭代去打印堆（數(shù)組）
Iterator<Integer> iterator1 = priorityQueue1.iterator();
while(iterator1.hasNext()){
System.out.print(iterator1.next()+" ");
}
System.out.println();
//
List<Integer> arraylist = new ArrayList<>();
arraylist.add(27);
arraylist.add(15);
arraylist.add(19);
arraylist.add(18);
arraylist.add(28);
arraylist.add(34);
arraylist.add(65);
arraylist.add(49);
arraylist.add(25);
arraylist.add(37);
Queue<Integer> priorityQueue2 = new PriorityQueue<>(arraylist);
Iterator<Integer> iterator2 = priorityQueue1.iterator();
while(iterator2.hasNext()){
System.out.print(iterator2.next()+" ");
}
System.out.println();
}
}
結果
2.5PriorityQueue的基本方法
boolean add(E e)
將指定的元素插入到此優(yōu)先級隊列中。
void clear()
從此優(yōu)先級隊列中清空所有元素。
Comparator<? super E> comparator()
返回用于為了在這個隊列中的元素，或比較null如果此隊列根據(jù)所述排序natural ordering的元素。
boolean contains(Object o)
如果此隊列包含指定的元素，則返回 true 。
Iterator<E> iterator()
返回此隊列中的元素的迭代器。
boolean offer(E e)
將指定的元素插入到此優(yōu)先級隊列中。
與addq區(qū)別在于add堆滿時直接拋出異常，而offer會自動擴容并且返回false;
E peek()
檢索但不刪除此隊列的頭，如果此隊列為空，則返回 null 。
E poll()
檢索并刪除此隊列的頭，如果此隊列為空，則返回 null 。
boolean remove(Object o)
從該隊列中刪除指定元素的單個實例（如果存在）。
int size()
返回此集合中的元素數(shù)。
Spliterator<E> spliterator()
在此隊列中的元素上創(chuàng)建late-binding和失敗快速 Spliterator 。
Object[] toArray()
返回一個包含此隊列中所有元素的數(shù)組。
<T> T[] toArray(T[] a)
返回一個包含此隊列中所有元素的數(shù)組; 返回的數(shù)組的運行時類型是指定數(shù)組的運行時類型。
2.6PriorityQueue的擴容機制
以下是原生PriorityQueue的擴容原碼
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//數(shù)組的最大長度是Integer所能表示的最大值減8
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :
(oldCapacity >> 1));
//從這個三目運算符就可以看出擴容的機制。
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)//如果新的容量比數(shù)組的最大容量還要大
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
優(yōu)先級隊列的擴容說明：
如果容量小于64時，是按照oldCapacity的2倍方式擴容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式擴容的
如果容量超過MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE來進行擴容
2.7集合框架中PriorityQueue的比較方式
集合框架中的PriorityQueue底層使用堆結構，因此其內部的元素必須要能夠比大小，PriorityQueue采用了：
Comparble和Comparator兩種方式。
- Comparble是默認的內部比較方式，如果用戶插入自定義類型對象時，該類對象必須要實現(xiàn)Comparble接口，并覆寫compareTo方法
- 用戶也可以選擇使用比較器對象，如果用戶插入自定義類型對象時，必須要提供一個比較器類，讓該類實現(xiàn)Comparator接口并覆寫compare方法。
java JDK中關于comparable和comparator的一些原生代碼
// JDK中PriorityQueue的實現(xiàn)：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
// ...
// 默認容量
private static ?nal int DEFAULT_INITIAL_CAPACITY = 11;
// 內部定義的比較器對象，用來接收用戶實例化PriorityQueue對象時提供的比較器對象
private ?nal Comparator<? super E> comparator;
// 用戶如果沒有提供比較器對象，使用默認的內部比較，將comparator置為null
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 如果用戶提供了比較器，采用用戶提供的比較器進行比較
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// ...
// 向上調整：
// 如果用戶沒有提供比較器對象，采用Comparable進行比較
// 否則使用用戶提供的比較器對象進行比較
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// 使用Comparable
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
// 使用用戶提供的比較器對象進行比較
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
}
我們可以實際操作來看一下底層的運行邏輯
Queue<Integer> priorityQueue1 = new PriorityQueue<>();
priorityQueue1.offer(27);
priorityQueue1.offer(15);
那么底層實際上是如下圖這樣運行的
而這里面調用的comparaTo實際上應該是在Integer類里面進行了覆寫
2.8使用PriorityQueue創(chuàng)建大小堆，解決TOPK問題
2.8.1問題背景
假如說某市進行了一次統(tǒng)考，有很多學生（數(shù)據(jù)量很大），那么我們如何在眾多學生中迅速找到這次考試中成績最好的50人呢？
這就要用到堆這樣的數(shù)據(jù)結構了。我們將問題簡化，假如有7個學生，怎么去找前k名，或者怎么找k個分數(shù)最大值、怎么找第k大值。同理又怎么去找分數(shù)最低的k名學生。
2.8.2解決辦法
2.8.1找k個最大值
先來說找k個分數(shù)最大值
我們可以定義一個只有k個元素的PriorityQueue,將7和元素順序插入，在插入k后（比如說k = 3）那么我們得到結果3的元素的小根堆，并且此時堆頂元素是當前三個元素中最小的，那么我們再入堆時，就將該元素與堆頂元素進行比較，如果比堆頂大，那么就證明他在當前最大的數(shù)值這個集合中，我們就入堆，否則不如堆，繼續(xù)往后。
此時這個思路里面的比較就需要我們重寫comparable方法或者自己定義一個comparator比較器了。
具體代碼如下
先定義一個學生類實現(xiàn)Comparable接口并且重寫comparaTo方法
public class student implements Comparable<student>{
String name;
int age;
double score;
public student(String name, int age, double score) {
this.name = name;
this.age = age;
this.score = score;
}
@Override
//重寫comparableTo方法
public int compareTo(student o) {
return (int)(this.score-o.score);
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
student student1 = new student("a", 27, 27.0);
student student2 = new student("b", 15, 15.0);
student student3 = new student("c", 19, 19.0);
student student4 = new student("d", 18, 18.0);
student student5 = new student("e", 28, 28.0);
student student6 = new student("f", 34, 34.0);
student student7 = new student("g", 65, 65.0);
ArrayList<student> arrayList = new ArrayList<>();
arrayList.add(student1);
arrayList.add(student2);
arrayList.add(student3);
arrayList.add(student4);
arrayList.add(student5);
arrayList.add(student6);
arrayList.add(student7);
PriorityQueue<student> priorityQueue1 = new PriorityQueue<>(3);
int i = 0;
while(i<3){
priorityQueue1.offer(arrayList.get(i));
i++;
}
while(i<arrayList.size()){
if(arrayList.get(i).score>priorityQueue1.peek().score){
priorityQueue1.poll();
priorityQueue1.offer(arrayList.get(i));
i++;
}
else{
i++;
}
}
System.out.println();
}
測試結果
我們發(fā)現(xiàn)preorityqueue里面確實是成績最高的三名學生
2.8.2找k個最小值
找k個最小值與找k個最大值的區(qū)別無非就在于要建立的是大根堆，每次都是比堆頂元素小才會入堆。
非常簡單，只需要將comparaTo方法調轉一下就可以。
student類的定義：
public class student implements Comparable<student>{
String name;
int age;
double score;
public student(String name, int age, double score) {
this.name = name;
this.age = age;
this.score = score;
}
@Override
//重寫comparableTo方法
public int compareTo(student o) {
return (int)(o.score-this.score);
}
}
主函數(shù)
import java.util.*;
public class Main {
public static void main(String[] args) {
student student1 = new student("a", 27, 27.0);
student student2 = new student("b", 15, 15.0);
student student3 = new student("c", 19, 19.0);
student student4 = new student("d", 18, 18.0);
student student5 = new student("e", 28, 28.0);
student student6 = new student("f", 34, 34.0);
student student7 = new student("g", 65, 65.0);
ArrayList<student> arrayList = new ArrayList<>();
arrayList.add(student1);
arrayList.add(student2);
arrayList.add(student3);
arrayList.add(student4);
arrayList.add(student5);
arrayList.add(student6);
arrayList.add(student7);
PriorityQueue<student> priorityQueue1 = new PriorityQueue<>(3);
int i = 0;
while(i<3){
priorityQueue1.offer(arrayList.get(i));
i++;
}
while(i<arrayList.size()){
if(arrayList.get(i).score<priorityQueue1.peek().score){
priorityQueue1.poll();
priorityQueue1.offer(arrayList.get(i));
i++;
}
else{
i++;
}
}
System.out.println();
}
}
測試結果
2.8.3利用比較器構建大根堆
其實，PriorityQueue除了支持前面介紹過的三種構造方法外，其實還支持比較器作為參數(shù)參與構造，有以下兩種
PriorityQueue(Comparator<? super E> comparator)
創(chuàng)建具有默認初始容量（11）的 PriorityQueue ，并根據(jù)指定的比較器對其元素進行排序。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
創(chuàng)建具有 PriorityQueue初始容量的PriorityQueue，根據(jù)指定的比較器對其元素進行排序。
所以，除了student類實現(xiàn)comparable接口，重寫compareTo方法，還可以自己創(chuàng)建一個比較器類，實現(xiàn)comparator接口，重寫compare方法。然后實例化這個對象，將帶實例化對象作為實參傳入priorityqueue的構造函數(shù)。
比如下面就是采用重新構造比較器的形式去建立大根堆，去結果上述topK問題。
示例：
student類的定義
public class student {
String name;
int age;
double score;
public student(String name, int age, double score) {
this.name = name;
this.age = age;
this.score = score;
}
}
Main類
//構建一個用于大根創(chuàng)建的比較器
class maxScoreComprator implements Comparator<student>{
@Override
public int compare(student o1, student o2) {
return (int)(o2.score- o1.score);
}
}
public class Main {
public static void main(String[] args) {
student student1 = new student("a", 27, 27.0);
student student2 = new student("b", 15, 15.0);
student student3 = new student("c", 19, 19.0);
student student4 = new student("d", 18, 18.0);
student student5 = new student("e", 28, 28.0);
student student6 = new student("f", 34, 34.0);
student student7 = new student("g", 65, 65.0);
ArrayList<student> arrayList = new ArrayList<>();
arrayList.add(student1);
arrayList.add(student2);
arrayList.add(student3);
arrayList.add(student4);
arrayList.add(student5);
arrayList.add(student6);
arrayList.add(student7);
maxScoreComprator com1 = new maxScoreComprator();
PriorityQueue<student> priorityQueue1 = new PriorityQueue<student>(3,com1);//將比較器作為實參傳入
int i = 0;
while(i<3){
priorityQueue1.offer(arrayList.get(i));
i++;
}
while(i<arrayList.size()){
if(arrayList.get(i).score<priorityQueue1.peek().score){
priorityQueue1.poll();
priorityQueue1.offer(arrayList.get(i));
i++;
}
else{
i++;
}
}
System.out.println();
}
}
測試結果
此外還可以簡化以下傳比較器時采用匿名內部類的形式
PriorityQueue<student> priorityQueue1 = new PriorityQueue<student>(3,new Comparator<student>() {
@Override
public int compare(student o1, student o2) {
return (int) (o2.score - o1.score);
}
});
三、堆排序
3.1問題背景
有一組數(shù)據(jù)：
27,15,191,18,28,34,65,49,25,37，對這一組數(shù)據(jù)按照從小到大排序
3.2誤區(qū)
我們想用堆排序去解決，那么首先要確定的就是用大根堆還是小根堆呢？
一定要注意堆排序要想從大到小輸出一組數(shù)據(jù)，用的不是大根堆，而是小根堆。因為實際上堆這個數(shù)據(jù)結構本身只有堆頂元素有排序意義，因為左右子樹是并不知道誰大誰小的。如果用小根堆，我們只能建立另外一個數(shù)組，然后每次用這個數(shù)組去接受堆頂元素，每出堆一個就再次調整堆，這樣無論是時間復雜度還是空間復雜度都是比較高的。
那么如何用小根堆得到從大到小的排序呢
3.3解決辦法
- 我們得到一個數(shù)組，先將其調整為小根堆，這樣堆頂元素就是這里面最小的元素了；
- 將堆頂元素與堆尾元素值互換，這樣最小的元素就調整到了數(shù)組末尾；
- 然后再次調整至小根堆（排除掉最后一個元素進行調整），這樣堆頂元素就是第二小元素以此重復。
3.4具體代碼實現(xiàn)
堆排序的定義
//堆排序
public void heapSort(){
int end = useSize-1;
while(end>0){
swap(elem,0,end);
shiftDown(0,end);//向下調整，具體代碼看前面堆的模擬實現(xiàn)
end--;
}
}
//交換
private void swap(int[] elem,int x,int y){
int tmp = elem[x];
elem[x] = elem[y];
elem[y] = tmp;
}
測試代碼
public class HeapSort {
public static void main(String[] args) {
int[] arr = {27,15,191,18,28,34,65,49,25,37};
TestHeap heap = new TestHeap();
heap.initElem(arr);//初始化，具體細節(jié)可以看前面堆的模擬實現(xiàn)
heap.createShortHeap();//構建小根堆，具體細節(jié)可以看前面堆的模擬實現(xiàn)
heap.heapSort();
System.out.println();
}
}
結果
文章來源：http://www.zghlxwxcb.cn/news/detail-719595.html
3.5執(zhí)行過程圖示
至此，java堆的詳解就暫告一段落啦！文章來源地址http://www.zghlxwxcb.cn/news/detail-719595.html
到了這里，關于java 堆（優(yōu)先級隊列）詳解的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
