溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“Java數據結構之優先級隊列實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“Java數據結構之優先級隊列實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
堆的定義：n個元素的序列{k1 , k2 , … , kn}稱之為堆，當且僅當滿足以下條件時：
（1）ki >= k2i 且 ki >= k(2i+1) ——大根堆
（2） ki <= k2i 且 ki <= k(2i+1) ——小根堆
簡單來說：
堆是具有以下性質的完全二叉樹：
（1）每個結點的值都大于或等于其左右孩子結點的值，稱為大根堆（如左下圖）；
或者：
（1）每個結點的值都小于或等于其左右孩子結點的值，稱為小根堆（如右下圖）。
我們使用數組保存二叉樹結構，即是將二叉樹用層序遍歷方式放入數組中，如上圖。
堆的元素下標存在以下關系：
1.假如已知雙親（parent）的下標，則
左孩子（left）下標 = 2parent + 1；
右孩子（right）下標 = 2parent +2；
2.已知孩子（child）（不區分左右）下標，則：
雙親（parent）下標 = （child - 1）/ 2 ;
小結：
堆邏輯上是一棵完全二叉樹；
堆物理上保存在數組中；
滿足任意結點的值都大于其子樹中結點的值，叫做大堆，或者大根堆，或者最大堆；反之，則是小堆，或者小根堆，或者最小堆；
堆的基本作用是，快速找集合中的最值。
設有一個無序序列 {2,5,7,8,4,6,3,0,9,1 }，下面通過圖解來建初始堆。
這里有一個前提：這棵二叉樹的左右子樹都必須是一個堆，才能進行調整。
下面是用到的數據的一些說明：
array 代表存儲堆的數組
size 代表數組中被視為堆數據的個數
index 代表要調整位置的下標
left 代表 index 左孩子下標
right 代表 index 右孩子下標
min 代表 index 的最小值孩子的下標
過程文字描述如下：
1.index 如果已經是葉子結點，則整個調整過程結束：
（1）判斷 index 位置有沒有孩子；
（2） 因為堆是完全二叉樹，沒有左孩子就一定沒有右孩子，所以判斷是否有左孩子；
（3） 因為堆的存儲結構是數組，所以判斷是否有左孩子即判斷左孩子下標是否越界，即 left >= size 越界。
2.確定 left 或 right，誰是 index 的最小孩子 min：
（1） 如果右孩子不存在，則 min = left；
（2）否則，比較 array[left] 和 array[right] 值得大小，選擇小的為 min；
（3）比較 array[index] 的值 和 array[min] 的值，如果 array[index] <= array[min]，則滿足堆的性質，調整結束。
3.否則，交換 array[index] 和 array[min] 的值；
4.然后因為 min 位置的堆的性質可能被破壞，所以把 min 視作 index，向下重復以上過程。
通過上面的操作描述，我們寫出以下代碼：
public static void shiftDown(int[] array, int size, int index){
int left = 2*index +1;
while(left < size){
int min = left;
int right = 2*index +2;
if(right<size){
if(array[right] < array[left]){
min = right;
}
}
if(array[index] <= array[min]){
break;
}
int tmp = array[index];
array[index] = array[min];
array[min] = tmp;
index = min;
left = 2*index +1;
}
}時間復雜度為 O(log(n))。
下面我們給出一個數組，這個數組邏輯上可以看做一顆完全二叉樹，但是還不是一個堆，現在我們通過算法，把它構建成一個堆。根節點左右子樹不是堆，我們怎么調整呢？這里我們從倒數的第一個非葉子節點的子樹開始調整，一直調整到根節點的樹，就可以調整成堆。
時間復雜度分析：
粗略估算，可以認為是在循環中執行向下調整，為 O(n * log(n))，（了解）實際上是 O(n)。
//建堆代碼
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根據代碼 顯示的時間復雜度 看起來 應該是O(n*logn) 但是 實際上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//調整
shiftDown(parent,usedSize);
}
}根據百科解釋：
普通的隊列是一種先進先出的數據結構，元素在隊列尾追加，而從隊列頭刪除。在優先隊列中，元素被賦予優先級。當訪問元素時，具有最高優先級的元素最先刪除。優先隊列具有最高級先出（first in, largest out）的行為特征。通常采用堆數據結構來實現。
所以我們在這里實現優先隊列的內部原理是堆，也就是說采用堆來構建。
過程（以大堆為例）：
首先按尾插方式放入數組；
比較其和其雙親的值的大小，如果雙親的值大，則滿足堆的性質，插入結束；
否則，交換其和雙親位置的值，重新進行 2、3 步驟；
直到根結點。
下面圖解：
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}為了防止破壞堆的結構，刪除時并不是直接將堆頂元素刪除，而是用數組的最后一個元素替換堆頂元素，然后通過向 下調整方式重新調整成堆。
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//擴容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意這里傳入的是usedSize-1
shiftUp(usedSize-1);
}直接返回堆頂元素
public int peek() {
if(isEmpty()) {
throw new RuntimeException("優先級隊列為空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}整體的代碼：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap() {
this.elem = new int[10];
}
/**
* 向下調整函數的實現
* @param parent 每棵樹的根節點
* @param len 每棵樹的調整的結束位置 10
*/
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起碼 是有左孩子的，至少有1個孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保證當前左右孩子最大值的下標
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
public void createHeap(int[] array) {
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
usedSize++;
}
//根據代碼 顯示的時間復雜度 看起來 應該是O(n*logn) 但是 實際上是O(n)
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
//調整
shiftDown(parent,usedSize);
}
}
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public void offer(int val) {
if(isFull()) {
//擴容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//注意這里傳入的是usedSize-1
shiftUp(usedSize-1);
}
public boolean isFull() {
return usedSize == elem.length;
}
public int poll() {
if(isEmpty()) {
throw new RuntimeException("優先級隊列為空！");
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
usedSize--;
shiftDown(0,usedSize);
return tmp;
}
public int peek() {
if(isEmpty()) {
throw new RuntimeException("優先級隊列為空！");
}
return elem[0];
}
public boolean isEmpty() {
return usedSize == 0;
}
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
}什么是TopK問題？
從arr[1, n]這n個數中，找出最大的k個數，這就是經典的TopK問題。
解決這類問題，我們往往會有以下幾種思路：
對整體進行排序，輸出前10個最大的元素。
用上面剛剛講的堆。
也是用堆，不過這比第二個思路更巧妙。
我們直接講思路三：
先用前k個元素生成一個小頂堆，這個小頂堆用于存儲，當前最大的k個元素。
接著，從第k+1個元素開始掃描，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂，則替換堆頂的元素，并調整堆，以保證堆內的k個元素，總是當前最大的k個元素。
直到，掃描完所有n-k個元素，最終堆中的k個元素，就是所要求的TopK。
以這個數組{12，15，21，41，30}為例，找到前3個最大的元素。
那如果是將一組進行從小到大排序，我們該采用大根堆還是小根堆？
答案是：大根堆！
步驟如下：
將這組數據調整為大根堆調整為大根堆；
0下標和最后1個未排序的元素進行交換即可；
重復1、2，直到結束。
如果求前K個最大的元素，要建一個小根堆。如果求前K個最小的元素，要建一個大根堆。第K大的元素。建一個小堆，堆頂元素就是第K大的元素。第K小的元素。建一個大堆，堆頂元素就是第K小的元素。
public void heapSort() {
int end = this.usedSize-1;
while (end > 0) {
int tmp = elem[0];
elem[0] = elem[end];
elem[end] = tmp;
shiftDown(0,end);
end--;
}
}
public void shiftDown(int parent,int len) {
int child = 2*parent+1;
//1、最起碼 是有左孩子的，至少有1個孩子
while (child < len) {
if(child+1 < len && elem[child] < elem[child+1]) {
child++;//保證當前左右孩子最大值的下標
}
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}讀到這里，這篇“Java數據結構之優先級隊列實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
