[TOC] ## 優先隊列及堆排序 優先隊列是一種能完成以下任務的隊列：插入一個數值，取出最小或最大的數值（獲取數值，并且刪除）。 優先隊列可以用二叉樹來實現，我們稱這種結構為二叉堆 最小堆和最大堆是二叉堆的一種，是一棵完全二叉樹（一種平衡樹）。 最小堆的性質： 1. 父節點的值都小于左右兒子節點。 2. 這是一個遞歸的性質。 最大堆的性質： 1. 父節點的值都大于左右兒子節點。 2. 這是一個遞歸的性質。 最大堆和最小堆實現方式一樣，只不過根節點一個是最大的，一個是最小的 ### 最大堆特征 最大堆實現細節(兩個操作)： 1. push：向堆中插入數據時，首先在堆的末尾插入數據，如果該數據比父親節點還大，那么交換，然后不斷向上提升，直到沒有大小顛倒為止。 2. pop：從堆中刪除最大值時，首先把最后一個值復制到根節點上，并且刪除最后一個數值，然后和兒子節點比較，如果值小于兒子，與兒子節點交換，然后不斷向下交換， 直到沒有大小顛倒為止。在向下交換過程中，如果有兩個子兒子都大于自己，就選擇較大的。 最大堆有兩個核心操作，一個是上浮，一個是下沉，分別對應`push`和`pop`