1.優(yōu)先隊(duì)列：

能夠完成以下兩個(gè)操作的數(shù)據(jù)結(jié)構(gòu)叫優(yōu)先隊(duì)列：

可以插入新元素

可以快速取出所有元素的最值。

2.優(yōu)先隊(duì)列的實(shí)現(xiàn)：堆

堆是一顆完全二叉樹(shù)。

重要的性質(zhì)：父節(jié)點(diǎn)一定是其所有子孫節(jié)點(diǎn)的最值。

一個(gè)簡(jiǎn)單的堆的示意圖如下：

堆的插入：首先在堆的末尾插入該數(shù)值，然后不斷向上調(diào)整，直到?jīng)]有大小顛倒為止

取出最值：最值就在堆頂，即二叉樹(shù)的第一個(gè)元素。

刪除最值：首先將堆的最后一個(gè)元素復(fù)雜到根節(jié)點(diǎn)，并刪除最后一個(gè)元素，然后將根節(jié)點(diǎn)不斷向下進(jìn)行調(diào)整直到?jīng)]有大小顛倒。

時(shí)間復(fù)雜度：堆的插入和刪除的時(shí)間復(fù)雜度為O(l o g?n)O(log?n)O(log?n)

注意：刪除和插入具體的向上/下調(diào)整的方法，可以看下面的代碼。

3.代碼

優(yōu)先隊(duì)列的實(shí)現(xiàn)：我們知道完全二叉是可以通過(guò)簡(jiǎn)單的數(shù)值實(shí)現(xiàn)的，如果我們將完全二叉樹(shù)中的每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)從1開(kāi)始，編號(hào)順序是從上到下從左到右，然后根據(jù)這個(gè)編號(hào)將樹(shù)中的節(jié)點(diǎn)存儲(chǔ)到數(shù)組中，父子關(guān)系可以通過(guò)下面方式得到：

假設(shè)當(dāng)前節(jié)點(diǎn)的編號(hào)(數(shù)組中的編號(hào))為i ii，則有：

它的父節(jié)點(diǎn)的編號(hào)為：i/2 i/2i/2(整除)

它的左兒子節(jié)點(diǎn)的編號(hào)為：2∗i 2*i2∗i

它的右兒子節(jié)點(diǎn)的編號(hào)為：2∗i+1 2*i+12∗i+1

//最小堆的實(shí)現(xiàn)
#include <iostream>
#define Max_N   1005

using namespace std;

int Heap_size;
int Heap[Max_N];

//插入操作
void push(int x)
{
    int indx=++Heap_size;//首先插入到最后一個(gè)位置
    //向上調(diào)整
    while(indx>1)//只有i>1才會(huì)有父節(jié)點(diǎn)
    {
        int parent_indx=indx/2;//父節(jié)點(diǎn)編號(hào)
        if(Heap[parent_indx]<=x)//沒(méi)有上下顛倒就結(jié)束調(diào)整
            break;
        Heap[indx]=Heap[parent_indx];//大小顛倒就將當(dāng)前節(jié)點(diǎn)上調(diào)
        indx=parent_indx;

    }
    Heap[indx]=x;
}

//刪除操作
int pop()
{
    int result=Heap[0];//獲取最值
    int x=Heap[--Heap_size];//相當(dāng)于將最后的一個(gè)元素放到根節(jié)點(diǎn)
    int index=1;
    while(2*index<=Heap_size)//一定要有子節(jié)點(diǎn)
    {
        int L_son_index=2*index;
        int R_son_index=2*index+1;
        //比較兒子節(jié)點(diǎn)的最值
        int Min_index=L_son_index;
        if(R_son_index<=Heap_size && Heap[R_son_index]<Heap[Min_index])
            Min_index=R_son_index;
        //如果沒(méi)有上下顛倒就結(jié)束
        if(Heap[Min_index]>=x)
            break;
        //上下顛倒就交換
        Heap[index]=Heap[Min_index];
        index=Min_index;
    }
    Heap[index]=x;
    return result;
}

void Build_Heap(int data[],int n)
{
    //創(chuàng)建一個(gè)空堆
    Heap_size=0;
    for(int i=0;i<n;i++)//逐個(gè)插入元素
        push(data[i]);

}


int main()
{
    int n;
    int data[Max_N];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>data[i];
    cout<<"使用下面數(shù)據(jù)構(gòu)建堆"<<endl;
    for(int i=0;i<n;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    Build_Heap(data,n);
    cout<<"堆中數(shù)據(jù)："<<endl;
    for(int i=1;i<=Heap_size;i++)
        cout<<Heap[i]<<" ";
    cout<<endl;
    return 0;
}
/*
9
9 7 10 4 5 19 23 6 7
*/

4.優(yōu)先隊(duì)列的庫(kù)：

實(shí)際上，大部分情況并不需要自己使用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，我們可以使用C++中，STL里面的priority_queue來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。

以上就是動(dòng)力節(jié)點(diǎn)小編介紹的"優(yōu)先隊(duì)列的詳解"，希望對(duì)大家有幫助，想了解更多可查看Java教程。動(dòng)力節(jié)點(diǎn)在線(xiàn)學(xué)習(xí)教程，針對(duì)沒(méi)有任何Java基礎(chǔ)的讀者學(xué)習(xí),讓你從入門(mén)到精通,主要介紹了一些Java基礎(chǔ)的核心知識(shí)，讓同學(xué)們更好更方便的學(xué)習(xí)和了解Java編程，感興趣的同學(xué)可以關(guān)注一下。