數據結構與算法面試專題—

完全二叉樹

完全二叉樹中如果每棵子樹的最大值都在頂部就是大根堆
完全二叉樹中如果每棵子樹的最小值都在頂部就是小根堆

設計目標：完全二叉樹的設計目標是高效地利用存儲空間，同時便于進行層次遍歷和數組存儲。它的結構使得每個節點的子節點都可以通過簡單的計算得到，從而實現快速的節點訪問。

實現原理：完全二叉樹是一棵滿二叉樹，除了最后一層外，每一層都被完全填充。最后一層的節點都集中在左邊。這種結構可以用數組來存儲，其中數組的索引對應節點的位置。例如，對于索引為i的節點，其左子節點的索引為2i+1，右子節點的索引為2i+2，父節點的索引為(i-1)/2。

優點：空間利用率高，易于實現數組存儲。層次遍歷簡單，可以通過數組索引快速訪問節點。

缺點：插入和刪除節點可能比較耗時，特別是當需要保持完全二叉樹的結構時，可能需要重新調整整個結構。

堆結構

堆結構就是用數組實現的完全二叉樹結構

設計目標：堆結構的設計目標是實現高效的優先級隊列和排序算法。它基于完全二叉樹的結構，通過維護堆序性（父節點的值大于或等于子節點的值，或者小于或等于子節點的值）來實現快速的插入和刪除操作。

實現原理：堆結構通常用數組來實現，其中數組的索引對應節點的位置。在堆中，每個父節點的值都滿足一定的條件，例如最大堆中父節點的值大于或等于子節點的值，最小堆中父節點的值小于或等于子節點的值。插入操作通過在數組末尾添加元素，然后通過上浮（Percolate Up）來維護堆序性。刪除操作通常是指刪除堆頂元素，然后通過下沉（Percolate Down）來維護堆序性。

優點：插入和刪除操作的時間復雜度為O(log n)，在優先級隊列和排序算法中性能優越。空間利用率高，用數組實現簡單。

缺點：對于范圍查詢等操作不友好，無法高效地進行任意元素的查找和刪除操作。

如何理解“堆”？

堆本質是一種特殊的樹。關于這個樹，只要滿足兩點要求，它就是一個堆：

堆是一個完全二叉樹；
堆中每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值。

第一點，堆必須是一個完全二叉樹。完全二叉樹要求，除了最后一層，其他層的節點個數都是滿的，最后一層的節點都靠左排列。

第二點，堆中的每個節點的值必須大于等于（或者小于等于）其子樹中每個節點的值。實際上，我們還可以換一種說法，堆中每個節點的值都大于等于（或者小于等于）其左右子節點的值。這兩種表述是等價的。

對于每個節點的值都大于等于子樹中每個節點值的堆，我們叫作“大頂堆”。對于每個節點的值都小于等于子樹中每個節點值的堆，我們叫作“小頂堆”。

堆結構的`heapInsert`操作

將一個新元素插入到堆結構中，并維持堆的性質（即父節點的值大于或等于子節點的值，或者小于或等于子節點的值，視堆的類型而定）。

示例

假設有一個最大堆，堆數組為 [100, 85, 90, 80, 75, 70]，現在需要插入元素 95。

插入后數組變為 [100, 85, 90, 80, 75, 70, 95]。
新元素的位置是 6（從 0 開始計數）。
比較新元素與父節點（位置 (6-1)/2=2，值 90）：95 > 90，交換兩者位置，數組變為 [100, 85, 95, 80, 75, 70, 90]。
繼續比較新元素與新的父節點（位置 (2-1)/2=0，值 100）：95 < 100，無需交換。
插入完成，堆性質得以維持。

優點：能夠在 O(log n) 時間復雜度內完成插入操作。

缺點：需要調整堆的結構，可能導致多次數據交換。

堆結構的`heapify`操作

在堆結構中，當某個節點的子節點可能違反堆的性質時，通過調整該節點及其子節點，維持堆的性質。

示例

假設有一個最大堆，堆數組為 [95, 85, 90, 80, 75, 70]，現在需要對位置 0 的節點進行 heapify 操作。

該節點的值為 95，子節點為 85 和 90。
95 大于子節點，無需調整。
如果堆數組為 [75, 85, 90, 80, 75, 70]，需要對位置 0 的節點進行 heapify。
比較子節點 85 和 90，選擇較大的 90 作為候選。
交換 75 和 90，數組變為 [90, 85, 75, 80, 75, 70]。
繼續 heapify 位置 2 的節點（原來的 75）。
比較子節點 80 和 75，交換 75 和 80，數組變為 [90, 85, 80, 75, 75, 70]。
繼續 heapify 位置 3 的節點（原來的 75），沒有子節點，調整完成。

優點：能夠在 O(log n) 時間復雜度內完成調整操作。

缺點：需要遍歷節點的子節點，可能導致多次數據交換。

堆結構的增大

當堆中的元素數量增加，需要擴展堆的存儲空間。

通常使用動態數據結構，如動態數組或鏈表，來實現堆的動態增長。
當需要增大堆時，分配新的內存空間，并將原堆中的元素復制到新空間中。

示例

假設堆當前的存儲數組大小為 10，已滿。需要插入一個新元素，堆將自動增大到大小為 20。

堆結構的減少

當堆中的元素數量減少，可能需要縮小堆的存儲空間，以節省內存。

釋放堆中多余的存儲空間，調整存儲數組的大小。
可以通過動態數據結構的特性，如動態數組的收縮功能，實現堆的縮小。

示例

假設堆當前的存儲數組大小為 20，但只有 5 個元素。可以將堆縮小到大小為 10，釋放多余的空間。

優先級隊列結構

設計目標

優先級隊列的設計目標是允許高效地訪問和操作優先級最高的元素。與普通隊列中的先進先出（FIFO）原則不同，優先級隊列中的元素根據其優先級進行排序，并且優先級最高的元素會被優先處理。

實現原理

優先級隊列通常使用堆結構來實現，能夠高效地維護元素的優先級順序。

1. 插入操作（Enqueue）

將新元素添加到堆的末尾。

通過上浮（Percolate Up）操作，將新元素與父節點進行比較和交換，直到滿足堆的性質。

2. 刪除操作（Dequeue）

刪除堆頂元素（優先級最高的元素）。

將堆的最后一個元素移動到堆頂。

通過下沉（Percolate Down）操作，將該元素與子節點進行比較和交換，直到滿足堆的性質。

優點

插入和刪除操作的時間復雜度為 O(log n)，在需要動態維護優先級的場景中性能優越。

空間利用率高，可以用數組實現，節省存儲空間。

缺點

不支持高效的隨機訪問和查詢操作，無法快速找到任意元素。

對于某些操作（如批量插入），可能需要重新構建整個堆，導致較高的開銷。

堆排序

堆排序是一種原地的、時間復雜度為O(n log n)的排序算法。

堆排序不是穩定的排序算法，因為在排序的過程，存在將堆的最后一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。

實現步驟

先讓整個數組都變成大根堆結構，建立堆的過程:?
1. 從上到下的方法，時間復雜度為O(N * logN)?
2. 從下到上的方法，時間復雜度為O(N)?
把堆的最大值和堆末尾的值交換，然后減少堆的大小之后，再去調整堆，一直周而復始，時間復雜度為O(N * logN)?
堆的大小減小成0之后，排序完成

實現代碼

    /*** 對給定的整數數組進行堆排序。* 堆排序是一種基于堆數據結構的排序算法，它的時間復雜度為O(N log N)，空間復雜度為O(1)。** @param arr 待排序的整數數組*/public void heapSort(int[] arr) {// 如果數組為空或者長度小于2，直接返回，因為不需要排序if (arr == null || arr.length < 2) {return;}// O(N*logN)// 從數組的最后一個元素開始，依次將每個元素調整為大根堆for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, arr.length);}// 初始化堆的大小為數組的長度int heapSize = arr.length;// 將堆頂元素（最大值）與堆的最后一個元素交換，并將堆的大小減1swap(arr, 0, --heapSize);// O(N*logN)// 當堆的大小大于0時，繼續進行排序while (heapSize > 0) { // O(N)// 將堆頂元素調整為大根堆heapify(arr, 0, heapSize); // O(logN)// 將堆頂元素（最大值）與堆的最后一個元素交換，并將堆的大小減1swap(arr, 0, --heapSize); // O(1)}}/*** 將指定索引位置的元素插入到堆中，并調整堆結構，使其滿足大根堆的性質。* 該方法會將新元素與其父節點比較，如果新元素大于父節點，則交換它們的位置，* 并繼續向上比較，直到新元素小于等于父節點或到達堆頂。** @param arr   包含堆元素的數組* @param index 要插入的元素的索引*/public void heapInsert(int[] arr, int index) {// 當當前元素大于其父節點時，交換它們的位置，并更新當前元素的索引while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}/*** 調整指定索引位置的元素，使其滿足大根堆的性質。* 該方法會將指定元素與其子節點比較，如果該元素小于其子節點中的最大值，* 則交換它們的位置，并繼續向下比較，直到該元素大于等于其子節點或到達葉子節點。** @param arr      包含堆元素的數組* @param index    要調整的元素的索引* @param heapSize 當前堆的大小*/public void heapify(int[] arr, int index, int heapSize) {// 計算左孩子的下標int left = index * 2 + 1; // 當左孩子存在時，繼續循環while (left < heapSize) { // 兩個孩子中，誰的值大，把下標給largest// 1）只有左孩子，left -> largest// 2) 同時有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest// 3) 同時有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest// 找出左右孩子中值較大的那個的下標int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// 比較父節點和較大孩子的值，將較大值的下標賦給largestlargest = arr[largest] > arr[index] ? largest : index;// 如果父節點已經是最大的，跳出循環if (largest == index) {break;}// 交換父節點和較大孩子的位置swap(arr, largest, index);// 更新當前節點的下標index = largest;// 計算新的左孩子的下標left = index * 2 + 1;}}/*** 交換數組中兩個指定索引位置的元素。** @param arr 包含元素的數組* @param i   第一個元素的索引* @param j   第二個元素的索引*/public void swap(int[] arr, int i, int j) {// 使用臨時變量交換兩個元素的值int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

過程分析

我們可以把堆排序的過程大致分解成兩個大的步驟，建堆和排序。

建堆

我們首先將數組原地建成一個堆。所謂“原地”就是，不借助另一個數組，就在原數組上操作。建堆的過程，有兩種思路。

第一種是在堆中插入一個元素。盡管數組中包含個數據，但是我們可以假設，起初堆中只包含一個數據，就是下標為1的數據。然后，我們調用插入操作，將下標從2到n的數據依次插入到堆中。這樣我們就將包含n個數據的數組，組織成了堆。

第二種實現思路，跟第一種截然相反。第一種建堆思路的處理過程是從前往后處理數組數據，并且每個數據插入堆中時，都是從下往上堆化。而第二種實現思路，是從后往前處理數組，并且每個數據都是從上往下堆化。

逐層調整，直到整個數組滿足堆的條件。

從最后一個非葉子節點開始，逐層向上進行 heapify 操作。
最后一個非葉子節點的索引為：floor((n-2)/2)，其中 n 是數組的長度。
使用 heapify 調整以該節點為根的子樹。

排序

建堆結束之后，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最后一個元素交換，那最大元素就放到了下標為n的位置。

當堆頂元素移除之后，我們把下標為n的元素放到堆頂，然后再通過堆化的方法，將剩下的n－1個元素重新構建成堆。堆化完成之后，我們再取堆頂的元素，放到下標是n一1的位置，一直重復這個過程，直到最后堆中只剩下標為1的一個元素，排序工作就完成了。

為什么快速排序要比堆排序性能好？

堆排序數據訪問的方式沒有快速排序友好

快速排序的數據訪問方式：

快速排序是基于分治法（Divide and Conquer）的排序算法。它通過選擇一個基準值（pivot），將數組劃分為兩個子數組，左側子數組的元素小于或等于基準值，右側子數組的元素大于或等于基準值。然后遞歸地對這兩個子數組進行排序。在分割過程中，快速排序對數組中的元素進行連續的比較和交換，這種操作在內存中的數據訪問模式通常是連續的，與現代計算機的緩存機制非常匹配。連續的內存訪問使得緩存命中率更高，減少了內存訪問的延遲，從而提高了排序的效率。
例如，當對一個已部分排序的數組進行快速排序時，基準值的選擇和分割操作會使得數組被分割為較小的子數組，而這些子數組在內存中是連續存儲的。對這些子數組進行遞歸排序時，緩存能夠有效地預取（cache prefetch）這些連續的數據，減少了從主存中加載數據的次數，加快了排序的速度。

堆排序的數據訪問方式：

堆排序依賴于堆數據結構，需要頻繁地訪問父節點和子節點。在堆排序過程中，數據的訪問模式是隨機的，無法充分利用內存的局部性原理。堆的父節點和子節點在內存中可能不是連續存儲的，因此訪問這些節點時，常常會導致緩存未命中。緩存未命中會增加內存訪問的延遲，降低排序的效率。
例如，在調整堆結構時，需要比較父節點和子節點的值，并根據比較結果進行交換。這種訪問模式使得數據在內存中的跳轉較為頻繁，無法像快速排序那樣利用緩存的預取特性，導致性能下降。

對于同樣的數據，在排序過程中，堆排序算法的數據交換次數要多于快速排序

快速排序的數據交換次數：

快速排序的平均時間復雜度為O(n log n)，其數據交換次數相對較少。在快速排序的分割過程中，每個元素會被交換到正確的位置，但整個過程中交換的次數通常比堆排序少。快速排序的遞歸結構使得大部分元素的比較和交換發生在較小的子數組中，減少了不必要的數據移動。
例如，對一個隨機分布的數組進行快速排序時，每次分割操作會使得元素被快速地放置在接近其最終位置的地方。這減少了后續排序過程中需要移動的數據量，從而降低了數據交換的總次數。

堆排序的數據交換次數：

堆排序的主要操作是構建堆和調整堆結構。在構建堆的過程中，需要多次比較和交換元素。每次插入或刪除元素時，堆結構的維護需要進行多次比較和交換，以確保父節點的值大于或等于子節點的值（對于最大堆而言）。在堆排序的整個過程中，數據交換的次數相對較多。
例如，當構建一個最大堆時，每個元素都需要與它的子節點進行比較和交換。如果一個元素的值小于它的子節點中的較大者，就需要交換它們的位置，并繼續對子節點進行調整。這個過程會涉及到多次數據交換，直到堆的性質被滿足。在堆排序的調整過程中，這樣的交換操作會頻繁發生，導致數據交換次數增加，從而影響了排序的性能。