在後台開發人員的面試中，有這麼一個經典的題目，我們有一堆定時任務，每個任務都有執行時間，這堆定時任務還有可能會不停的增加，要求我們設計一個數據結構與算法來實現，這個題目的經典答案，就是優先隊列，那麼優先隊列的原理是什麼呢？不知道你有沒有被問過這個問題，今天我們就來學習優先隊列的底層原理，是一個基礎數據結構，叫做堆（Heap），數據結構的堆跟内存堆棧的堆不是一回事，曾經面試一個同學，問他堆是一種什麼樣的數據結構，直接把内存堆棧的概念背誦出來了，真是讓人可笑不得。

我們直接開門見山，數據結構中堆（Heap）是什麼東西呢？這裡，通常，我們講的堆（Heap）都是二叉堆，堆是一顆完全二叉樹，如果一個堆的深度為h，那麼從第一層開始有1個節點，第二層有2個節點，第三層有4個節點，直到第h-1層有2^(h-2)個節點。我們把下圖這種父節點小于子節點的堆稱之為小根堆，反之，父節點都大于子節點的堆稱之為大根堆。

數據結構堆（Heap）的最大作用就是用來排序！我們以小根堆為例(以下操作均已小根堆為例)，查詢小根堆裡面最小的元素，直接取第一個元素即可，算法時間複雜度為O（1）。

我們需要注意的是，一個堆如果要删除某個元素，隻支持删除最頂部的元素！在堆裡面，左兒子跟右兒子大小是不确定的，這個是二叉堆跟二叉排序樹的一個區别（在數據結構二叉排序樹中，左兒子<本身<右兒子。後面我們再來介紹下二叉排序樹）。在堆中，删除頭部元素稱之為Pop，那麼堆裡面删除一個元素的算法是什麼樣子的呢。

我們先把最底層，最右邊的元素，移到第一個元素，然後跟兩個兒子比較大小，與較小的兒子交換位置因為17比65，32都小，所以把32跟17交換位置。

重複上面的算法，将32與23，45一起比較大小，23是三者之中最小，再次交換位置

重複上面的算法，将32與53進行比較，發現大小一緻，不用變化

所以，我們可以把堆的Pop操作算法總結如下：跟最後一個元素交換，從樹根開始，比較兒子節點，與最小的交換，直到沒有兒子或者比兒子更小，算法複雜度為O(LogN)。

在堆中，插入一個元素是什麼樣子的呢？我們先把元素插到堆的末尾，每次都與父親節點進行比較，如果比父親比它小，就跟他交換位置例如下圖，我們新增一個元素22，它先跟自己的父親節點32進行比較。

重複上述算法,22再與23進行比較，随後交換位置

最後我們又得到新的小根堆，每次插入一個算法的時間複雜度為O(LogN)

堆的操作就是這麼簡單，支持3種操作，堆頂元素，彈出堆頂元素Pop，插入新的元素Insert。他們的算法學會了麼？算法與數據結構，需要我們不停地練習，才能夠熟練掌握，我會經常收集各大公司地算法面試題，分享一下經典地解題思路，有興趣地話可以關注下我，關注下我的專欄。同名公衆号（沙茶敏碎碎念）

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!