大鸡吧在线,92久草视频观看体验,久久久一九厂

這部分我們介紹一種新的數(shù)據(jù)結(jié)構(gòu)堆（Heap），“堆”是實(shí)現(xiàn)“優(yōu)先隊(duì)列”的一個(gè)高效的數(shù)據(jù)結(jié)構(gòu)。首先，我們來認(rèn)識(shí)“優(yōu)先隊(duì)列”。

優(yōu)先隊(duì)列（priority queue）

“優(yōu)先隊(duì)列”是從下面的這種場景中抽象出來的數(shù)據(jù)結(jié)構(gòu)。

例：班級(jí)里要選一名同學(xué)代表全班參加程序編程競賽，此時(shí)我們只會(huì)關(guān)心第 1 名是誰，第 1 名本人不想?yún)①惲耍蛘哒f第 1 名因?yàn)槠渌蛩夭环蠀⒖假Y格，我們才考慮第 2 名，但也是從剩下的那些同學(xué)中挑出第 1 名。即當(dāng)前我們只關(guān)心當(dāng)前“最優(yōu)”的那個(gè)元素，第 2 名及其以后的同學(xué)都不考慮了。

“優(yōu)先隊(duì)列”相對(duì)于“普通隊(duì)列”而言?！捌胀?duì)列”的性質(zhì)是“先進(jìn)先出，后進(jìn)后出”?！皟?yōu)先隊(duì)列”由元素的優(yōu)先級(jí)決定出隊(duì)的順序。

普通隊(duì)列	優(yōu)先隊(duì)列
先進(jìn)先出，后進(jìn)后出。由進(jìn)入隊(duì)列的時(shí)間順序決定。	出隊(duì)順序與入隊(duì)順序無關(guān)，只與隊(duì)列中元素的優(yōu)先級(jí)有關(guān)，優(yōu)先級(jí)最高的元素最先出隊(duì)。

優(yōu)先隊(duì)列的主要操作

“優(yōu)先隊(duì)列”是一種抽象的數(shù)據(jù)結(jié)構(gòu)，有兩種“優(yōu)先隊(duì)列”。一種“優(yōu)先隊(duì)列”每次可以從中拿到我們定義下優(yōu)先級(jí)“最高”的元素，即“最大堆”、“大頂堆”、“大根堆”，另一種“優(yōu)先隊(duì)列”每次可以從中拿到我們定義下優(yōu)先級(jí)“最低”的元素，即“最小堆”、“小頂堆”、“小根堆”。如果沒有特別說明，我們下文所指的“優(yōu)先隊(duì)列”都是指每次可以拿到優(yōu)先級(jí)“最高”元素的優(yōu)先隊(duì)列。

“優(yōu)先隊(duì)列”的主要操作有：

1、入隊(duì)

2、出隊(duì)：優(yōu)先隊(duì)列的一個(gè)重要特點(diǎn)是：出隊(duì)的時(shí)候總是取出優(yōu)先級(jí)最高的那個(gè)元素。

如果不考慮時(shí)間復(fù)雜度，“優(yōu)先隊(duì)列”可以有以下兩種實(shí)現(xiàn)方式：“無序數(shù)組”和“有序數(shù)組”。

實(shí)現(xiàn)1：無序數(shù)組。放入的時(shí)候，直接放在數(shù)組的末尾，時(shí)間復(fù)雜度： $O(1)$ 。每次拿出元素之前，我們都排個(gè)序，或者像“選擇排序”那樣，把最大的那個(gè)拿出去就好了，時(shí)間復(fù)雜度是： $O(n)$ 。

實(shí)現(xiàn)2：有序數(shù)組。每次放入元素的時(shí)候，我們都排個(gè)序，像插入排序內(nèi)層循環(huán)那樣，保持?jǐn)?shù)組的有序性，時(shí)間復(fù)雜度 $O(n)$ ，把最大的那個(gè)拿出去 $O(1)$ 。

偉大的計(jì)算機(jī)科學(xué)家平衡了入隊(duì)和出隊(duì)這兩個(gè)操作的時(shí)間復(fù)雜度，這種數(shù)據(jù)結(jié)構(gòu)就是堆。

三種數(shù)據(jù)結(jié)構(gòu)對(duì)于實(shí)現(xiàn)優(yōu)先隊(duì)列的時(shí)間復(fù)雜度的比較

實(shí)現(xiàn)優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)	入隊(duì)操作	出隊(duì)操作
普通數(shù)組	$O(1)$	$O(n)$
順序數(shù)組	$O(n)$	$O(1)$
堆	$O(\log n)$	$O(\log n)$

說明： $\log n$ 表示以 $2$ 為底的 $n$ 的對(duì)數(shù)。

在 $N$ 個(gè)元素中選出前 $M$ 個(gè)元素。使用普通數(shù)組或者順序數(shù)組，最差的情況是 $O(N^2)$ ，使用堆可以將時(shí)間復(fù)雜度降到： $O(N\log M)$ 。事實(shí)上，時(shí)間復(fù)雜度是 $O(N^2)$ 與 $O(N\log M)$ 的差異巨大的。理解這個(gè)事實(shí)是我們掌握堆以及相關(guān)算法的基礎(chǔ)，正是因?yàn)槭褂枚堰@種數(shù)據(jù)結(jié)構(gòu)，提高了我們算法的執(zhí)行效率，我們才有必要來研究堆，使用堆。

我們發(fā)現(xiàn)，不管是“入隊(duì)”還是“出隊(duì)”，總有一個(gè)操作得把“優(yōu)先隊(duì)列”中的元素都看一遍。而“堆”就是這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)，能把 $O(n)$ 降到 $O(\log n)$ 。

綜上所述，“堆”是實(shí)現(xiàn)“優(yōu)先隊(duì)列”的高效的數(shù)據(jù)結(jié)構(gòu)?！岸选庇小白钚《选焙汀白畲蠖选保蜕厦嬉粯?，如果沒有特別說明，我們下文所指的“堆”都是指“最大堆”。

什么是“堆”

通過上一小節(jié)的介紹，我們可以看到堆的入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度都是 $O(\log n)$ ，因此我們可以猜測它的形狀看起來像是一棵樹一樣。

形如下面形狀的一個(gè)結(jié)構(gòu)就是“最大堆”。

堆與優(yōu)先隊(duì)列-1

“最大堆”的性質(zhì)：

首先，“最大堆”是一棵“完全二叉樹”。

完全二叉樹：從形狀上看，除了最后一層之外，其它層結(jié)點(diǎn)的數(shù)量達(dá)到最大值，并且最后一層的結(jié)點(diǎn)全部集中在左側(cè)。

“完全二叉樹”的特點(diǎn)是，可以使用一個(gè)數(shù)組保存“完全二叉樹”，而不必引入樹形結(jié)構(gòu)。這樣既可以利用數(shù)組元素可以快速訪問的特點(diǎn)，又讓結(jié)點(diǎn)和結(jié)點(diǎn)之間形成了“父”與“子”的結(jié)構(gòu)關(guān)系。

其次，任意一個(gè)結(jié)點(diǎn)，如果有孩子結(jié)點(diǎn)的話，孩子結(jié)點(diǎn)的值一定不會(huì)大于父親結(jié)點(diǎn)的值。

如果一個(gè)數(shù)組中的元素，有如上特點(diǎn)，我們稱之為堆有序。堆有序不是我們通常理解意義上的“升序”或者“降序”。如果把數(shù)組排成“完全二叉樹”的樣子，且滿足第 2 條，這個(gè)數(shù)組就是“堆有序”。這里要注意的是，通常我們數(shù)組的 $0$ 號(hào)索引不使用，從 $1$ 號(hào)索引開始使用，這只是一種習(xí)慣，因?yàn)檫@么做父子結(jié)點(diǎn)的索引關(guān)系更“好看”一些，僅此而已。到從 $0$ 號(hào)索引開始使用的堆也是可以的。

下面我們從索引從 1 號(hào)開始，自上到下、自左到右，標(biāo)記，即顯示成結(jié)點(diǎn)的旁邊黑色的數(shù)字，我們不難發(fā)現(xiàn)這些數(shù)字的排列形成的規(guī)律。正是因?yàn)椤岸选笔且豢谩巴耆鏄洹?，有如下的?guī)律，我們才可以很方便地索引數(shù)組中的位置，這就是我們?yōu)槭裁词褂脭?shù)組而不是使用樹來實(shí)現(xiàn)堆。

堆與優(yōu)先隊(duì)列-2

規(guī)律1：一個(gè)結(jié)點(diǎn)的左結(jié)點(diǎn)（如果有的話）的索引是這個(gè)結(jié)點(diǎn)的編號(hào)的 $2$ 倍；

規(guī)律2：一個(gè)結(jié)點(diǎn)的右結(jié)點(diǎn)（如果有的話）的索引是這個(gè)結(jié)點(diǎn)的編號(hào)的 $2$ 倍 $+ 1$ 。

從子結(jié)點(diǎn)索引找到父結(jié)點(diǎn)索引： ${\rm parent(i)}=\cfrac{i}{2}$ ，注意這里不能整除的時(shí)候需要向下取整。

從父節(jié)點(diǎn)索引找到兩個(gè)子結(jié)點(diǎn)索引： ${\rm left\ child = 2 \times i}$ ， ${\rm right\ child} = 2 \times i+1$ 。

這個(gè)兩條性質(zhì)不用記，我們只要拿一張紙，畫一個(gè)像上面一樣圖，就非常清楚了。到這里為止，我們可以先寫出“最大堆”的框架。

Python 代碼：

class MaxHeap:
    def __init__(self, capacity):
        # 我們這個(gè)版本的實(shí)現(xiàn)中，0 號(hào)索引是不存數(shù)據(jù)的，這一點(diǎn)一定要注意
        # 因?yàn)閿?shù)組從索引 1 開始存放數(shù)值
        # 所以開辟 capacity + 1 這么多大小的空間
        self.data = [None for _ in range(capacity + 1)]
        # 當(dāng)前堆中存儲(chǔ)的元素的個(gè)數(shù)
        self.count = 0
        # 堆中能夠存儲(chǔ)的元素的最大數(shù)量（為簡化問題，不考慮動(dòng)態(tài)擴(kuò)展）
        self.capacity = capacity

    def size(self):
        """
        返回最大堆中的元素的個(gè)數(shù)
        :return:
        """
        return self.count

    def is_empty(self):
        """
        返回最大堆中的元素是否為空
        :return:
        """
        return self.count == 0

Java 代碼：

public class MaxHeap {

    private int[] data;
    private int count; // 堆中真實(shí)元素的個(gè)數(shù)

    public MaxHeap(int capacity) {
        // 開辟數(shù)組空間（整個(gè)數(shù)組存儲(chǔ)從索引 1 開始）
        data = new int[capacity + 1];
        count = 0;
    }

    public int size() {
        return count;
    }
    // 當(dāng)前堆中的元素個(gè)數(shù)是否為 0
    public boolean isEmpty() {
        return count == 0;
    }
}

下面我們介紹如何保持“最大堆”數(shù)組的堆有序的性質(zhì)。

“最大堆”的第 1 個(gè)重要操作：向一個(gè)“最大堆”中添加元素

向“最大堆”中添加一個(gè)元素，對(duì)應(yīng)優(yōu)先隊(duì)列中“入隊(duì)”這個(gè)操作，同時(shí)還要保持“最大堆”的性質(zhì)，即根元素是“最大堆”中最大的元素，并且除了根結(jié)點(diǎn)以外任意一個(gè)結(jié)點(diǎn)不大于它的父親結(jié)點(diǎn)。這個(gè)操作叫做 shift up 。

向“最大堆”中的添加元素的時(shí)候，首先添加在數(shù)組的末尾，這是因?yàn)橐苿?dòng)次數(shù)最少，然后進(jìn)行調(diào)整，使得調(diào)整后的數(shù)組仍然滿足最大堆的性質(zhì)。

具體步驟如下：

1、新加的元素放在數(shù)組的末尾；

2、新加入的元素調(diào)整元素的位置：只與父結(jié)點(diǎn)比較（不必與兄弟孩子比較），如果比父結(jié)點(diǎn)大，就交換位置，否則，可以停止了，這個(gè)元素就放在當(dāng)前位置。

為什么我們要在數(shù)組的末尾添加一個(gè)元素呢？可不可以在開頭、中間？既然我們使用數(shù)組來實(shí)現(xiàn)堆，對(duì)數(shù)組添加一個(gè)元素來說，實(shí)現(xiàn)復(fù)雜度最低的操作就是在數(shù)組的末尾添加元素，如若不然，要讓數(shù)組中一部分的元素逐個(gè)后移，因此在數(shù)組的末尾加入元素是最自然的想法。但是在數(shù)組的末尾添加了一個(gè)元素，此時(shí)的數(shù)組就不滿足堆的定義（性質(zhì)），我們需要進(jìn)行一系列的操作，去維護(hù)堆的定義（性質(zhì)）。

如何維護(hù)堆的定義和性質(zhì)：通過 `shift up` 把新添加的元素放置到合適的位置

在數(shù)組的最后位置添加一個(gè)元素，新加入的元素只和父結(jié)點(diǎn)比較大?。o須和它的兄弟結(jié)點(diǎn)比較），只要比父結(jié)點(diǎn)大（嚴(yán)格大于），就往上走，否則停止，這個(gè)新添加的元素就放置在合適的位置，同時(shí)也調(diào)整了部分元素的位置。循環(huán)這樣做，這樣的過程叫做 shift up，shift up 也叫 swim，是“上浮”的意思。

Python 代碼：

def __shift_up(self, k):
    # 有索引就要考慮索引越界的情況，已經(jīng)在索引 1 的位置，就沒有必要上移了
    while k > 1 and self.data[k // 2] < self.data[k]:
        self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
        k //= 2

有索引就必須要考慮索引的邊界問題，就是這里說的 h > 1，因?yàn)楫?dāng) h = 1 的時(shí)候，元素已經(jīng)在堆頂， Shift Up 操作沒有意義。

另外和“插入排序”的優(yōu)化一樣，先存一下這個(gè)可能會(huì)上移的元素，通過逐層賦值，實(shí)現(xiàn)與逐層交換上移等價(jià)的操作。

Python 代碼：shift up 的過程可以轉(zhuǎn)化為多次賦值

def __swim(self, k):
    # 上浮，與父結(jié)點(diǎn)進(jìn)行比較
    temp = self.data[k]
    # 有索引就要考慮索引越界的情況，已經(jīng)在索引 1 的位置，就沒有必要上移了
    while k > 1 and self.data[k // 2] < temp:
        self.data[k] = self.data[k // 2]
        k //= 2
    self.data[k] = temp

shift up 是 insert 的一個(gè)子過程，有了 shift up ，insert 函數(shù)就可以很快寫出來：

Python 代碼：

def insert(self, item):
    if self.count + 1 > self.capacity:
        raise Exception('堆的容量不夠了')
    self.count += 1
    self.data[self.count] = item
    # 考慮將它上移
    self.__swim(self.count)

最大堆的第 2 個(gè)重要操作：向一個(gè)最大堆中取出元素

根據(jù)堆有序的性質(zhì)，根結(jié)點(diǎn)是堆（數(shù)組）中最大的元素，即索引為 $1$ 的元素。從最大堆中取出一個(gè)元素，即是取出根結(jié)點(diǎn)元素，同時(shí)還要保持最大堆的性質(zhì)。

根結(jié)點(diǎn)取出以后， $1$ 號(hào)索引位置為空，于是我們將當(dāng)前數(shù)組的最后一個(gè)元素放到 $1$ 號(hào)索引的位置，這樣做是因?yàn)榻粨Q和移動(dòng)的次數(shù)最少，這種想法也應(yīng)該是十分自然的，并且保持了完全二叉樹的性質(zhì)，但是此時(shí)數(shù)組并不滿足最大堆的性質(zhì)，我們就要進(jìn)行 shift down 的操作使這個(gè)數(shù)組保持最大堆的性質(zhì)。

shift down 的具體操作步驟：從 $1$ 號(hào)索引開始，如果存在右孩子，就把右孩子和左孩子比較，比出最大的那個(gè)，再和自己比較，如果比自己大，就交換位置，這樣的過程直到“不小于兩個(gè)孩子結(jié)點(diǎn)中的最大者”。

同理，我們可以寫出 shift down 的兩個(gè)版本：

Python 代碼：

def __shift_down(self, k):
    # 只要有左右孩子，左右孩子只要比自己大，就交換
    while 2 * k <= self.count:
        # 如果這個(gè)元素有左邊的孩子
        j = 2 * k
        # 如果有右邊的孩子，大于左邊的孩子，就好像左邊的孩子不存在一樣
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            j = j + 1
        if self.data[k] >= self.data[j]:
            break
        self.data[k], self.data[j] = self.data[j], self.data[k]
        k = j

說明：當(dāng)我們從 1 開始存放最大堆的元素的時(shí)候，最大堆的最后一個(gè)元素是 data[count]。

在完全二叉樹中，如何表示有孩子？其實(shí)有左孩子就夠了。這里的循環(huán)條件是 2 * k <= count ，等于號(hào)不能漏掉，自己手畫一個(gè)完全二叉樹就清楚了。

在結(jié)點(diǎn)存在子結(jié)點(diǎn)的情況下，先判斷是否存在右孩子，如果存在右孩子，就一定有左孩子，然后把右孩子和左孩子比較，比出最大的那個(gè)，再和自己比較，如果比自己大，就交換位置，這樣的過程直到“自己比左右兩個(gè)孩子都大”為止。

和上一節(jié) shift up 的優(yōu)化的思路一樣：逐漸下移的過程可以不用逐層交換，借用插入排序優(yōu)化的思路，多次賦值，一次交換。于是，我們有了版本 2 。

Python 代碼：

def __sink(self, k):
    # 下沉
    temp = self.data[k]
    # 只要它有孩子，注意，這里的等于號(hào)是十分關(guān)鍵的
    while 2 * k <= self.count:
        j = 2 * k
        # 如果它有右邊的孩子，并且右邊的孩子大于左邊的孩子
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            # 右邊的孩子勝出，此時(shí)可以認(rèn)為沒有左孩子
            j += 1
        # 如果當(dāng)前的元素的值，比右邊的孩子節(jié)點(diǎn)要大，則逐漸下落的過程到此結(jié)束
        if temp >= self.data[j]:
            break
        # 否則，交換位置，繼續(xù)循環(huán)
        self.data[k] = self.data[j]
        k = j
    self.data[k] = temp

shift down 是 extract_max 的一個(gè)子過程，有了 shift down，extract_max 函數(shù)就可以很快寫出來。

Python 代碼：

def extract_max(self):
    if self.count == 0:
        raise Exception('堆里沒有可以取出的元素')
    ret = self.data[1]
    self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
    self.count -= 1
    self.__sink(1)
    return ret

完整代碼：

Python 代碼：

# 通過 LeetCode 第 215 題、第 295 題測試
class MaxHeap:
    def __init__(self, capacity):
        # 我們這個(gè)版本的實(shí)現(xiàn)中，0 號(hào)索引是不存數(shù)據(jù)的，這一點(diǎn)一定要注意
        # 因?yàn)閿?shù)組從索引 1 開始存放數(shù)值
        # 所以開辟 capacity + 1 這么多大小的空間
        self.data = [None for _ in range(capacity + 1)]
        # 當(dāng)前堆中存儲(chǔ)的元素的個(gè)數(shù)
        self.count = 0
        # 堆中能夠存儲(chǔ)的元素的最大數(shù)量（為簡化問題，不考慮動(dòng)態(tài)擴(kuò)展）
        self.capacity = capacity

    def size(self):
        """
        返回最大堆中的元素的個(gè)數(shù)
        :return:
        """
        return self.count

    def is_empty(self):
        """
        返回最大堆中的元素是否為空
        :return:
        """
        return self.count == 0

    def insert(self, item):
        if self.count + 1 > self.capacity:
            raise Exception('堆的容量不夠了')
        self.count += 1
        self.data[self.count] = item
        # 考慮將它上移
        self.__swim(self.count)

    def __shift_up(self, k):
        # 有索引就要考慮索引越界的情況，已經(jīng)在索引 1 的位置，就沒有必要上移了
        while k > 1 and self.data[k // 2] < self.data[k]:
            self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
            k //= 2

    def __swim(self, k):
        # 上浮，與父結(jié)點(diǎn)進(jìn)行比較
        temp = self.data[k]
        # 有索引就要考慮索引越界的情況，已經(jīng)在索引 1 的位置，就沒有必要上移了
        while k > 1 and self.data[k // 2] < temp:
            self.data[k] = self.data[k // 2]
            k //= 2
        self.data[k] = temp

    def extract_max(self):
        if self.count == 0:
            raise Exception('堆里沒有可以取出的元素')
        ret = self.data[1]
        self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
        self.count -= 1
        self.__sink(1)
        return ret

    def __shift_down(self, k):
        # 只要有左右孩子，左右孩子只要比自己大，就交換
        while 2 * k <= self.count:
            # 如果這個(gè)元素有左邊的孩子
            j = 2 * k
            # 如果有右邊的孩子，大于左邊的孩子，就好像左邊的孩子不存在一樣
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                j = j + 1
            if self.data[k] >= self.data[j]:
                break
            self.data[k], self.data[j] = self.data[j], self.data[k]
            k = j

    def __sink(self, k):
        # 下沉
        temp = self.data[k]
        # 只要它有孩子，注意，這里的等于號(hào)是十分關(guān)鍵的
        while 2 * k <= self.count:
            j = 2 * k
            # 如果它有右邊的孩子，并且右邊的孩子大于左邊的孩子
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                # 右邊的孩子勝出，此時(shí)可以認(rèn)為沒有左孩子
                j += 1
            # 如果當(dāng)前的元素的值，比右邊的孩子節(jié)點(diǎn)要大，則逐漸下落的過程到此結(jié)束
            if temp >= self.data[j]:
                break
            # 否則，交換位置，繼續(xù)循環(huán)
            self.data[k] = self.data[j]
            k = j
        self.data[k] = temp


if __name__ == '__main__':
    max_heap = MaxHeap(6)
    max_heap.insert(3)
    print(max_heap.data[1])
    max_heap.insert(5)
    print(max_heap.data[1])
    max_heap.insert(1)
    print(max_heap.data[1])
    max_heap.insert(8)
    print(max_heap.data[1])
    max_heap.insert(7)
    print(max_heap.data[1])
    max_heap.insert(12)

    while not max_heap.is_empty():
        print('取出', max_heap.extract_max())

到這里，我們就可以通過“最大堆”實(shí)現(xiàn)排序功能了?！白钚《选笨梢匀绶ㄅ谥?。

我們已經(jīng)實(shí)現(xiàn)了最大堆的入隊(duì)和出隊(duì)兩個(gè)基本操作，我們完全通過直接輸出元素來檢驗(yàn)一下，自己寫出的最大堆是否符合最大堆的性質(zhì)。因?yàn)槊恳淮螐淖畲蠖讶〕龅目偸菙?shù)組中最大的元素，所以可以將最大堆用于排序。

優(yōu)先隊(duì)列的應(yīng)用

1、多路歸并排序

LeetCode 第 23 題：23. Merge k Sorted Lists；

傳送門：23. 合并K個(gè)排序鏈表；

題解：https://liweiwei1419.github.io/leetcode-solution/leetcode-0023-merge-k-sorted-lists/。

2、圖論中的最小生成樹算法；

3、圖論中的最短路徑算法；

4、哈夫曼樹與哈夫曼編碼；

另外，在 LeetCode 上使用堆解決的問題有：

LeetCode 第 451 題：根據(jù)字符出現(xiàn)頻率排序

LeetCode 第 703 題：數(shù)據(jù)流中的第K大元素

LeetCode 第 295 題：數(shù)據(jù)流的中位數(shù)

本文源代碼

Python：代碼文件夾，Java：代碼文件夾。

（本節(jié)完）

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

【算法日積月累】9-堆與優(yōu)先隊(duì)列

【算法日積月累】9-堆與優(yōu)先隊(duì)列

優(yōu)先隊(duì)列（priority queue）

更多優(yōu)先隊(duì)列在生活中的例子

優(yōu)先隊(duì)列的主要操作

三種數(shù)據(jù)結(jié)構(gòu)對(duì)于實(shí)現(xiàn)優(yōu)先隊(duì)列的時(shí)間復(fù)雜度的比較

什么是“堆”

“最大堆”的性質(zhì)：

“最大堆”的第 1 個(gè)重要操作：向一個(gè)“最大堆”中添加元素

如何維護(hù)堆的定義和性質(zhì)：通過 `shift up` 把新添加的元素放置到合適的位置

最大堆的第 2 個(gè)重要操作：向一個(gè)最大堆中取出元素

優(yōu)先隊(duì)列的應(yīng)用

本文源代碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

【算法日積月累】9-堆與優(yōu)先隊(duì)列

優(yōu)先隊(duì)列（priority queue）

更多優(yōu)先隊(duì)列在生活中的例子

優(yōu)先隊(duì)列的主要操作

三種數(shù)據(jù)結(jié)構(gòu)對(duì)于實(shí)現(xiàn)優(yōu)先隊(duì)列的時(shí)間復(fù)雜度的比較

什么是“堆”

“最大堆”的性質(zhì)：

“最大堆”的第 1 個(gè)重要操作：向一個(gè)“最大堆”中添加元素

如何維護(hù)堆的定義和性質(zhì)：通過 shift up 把新添加的元素放置到合適的位置

最大堆的第 2 個(gè)重要操作：向一個(gè)最大堆中取出元素

優(yōu)先隊(duì)列的應(yīng)用

本文源代碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

如何維護(hù)堆的定義和性質(zhì)：通過 `shift up` 把新添加的元素放置到合適的位置