前言

本文為本小白🤯學習數據結構的筆記，將以算法題為導向，向大家更清晰的介紹數據結構相關知識（算法題都出自🙌B站馬士兵教育——左老師的課程，講的很好，對于想入門刷題的人很有幫助👍）

上面寫完了歸并排序，快速排序，排序它本身整個算法并沒有什么，重要的是他的算法，它怎么提升時間復雜度，以及這種思想的應用，這是我們更要去關注的。下面來看一個新的排序——堆排序。

下面來介紹一下數據結構中的“堆”（Heap）。

1.堆 (Heap) 概述

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

• 堆是一棵完全二叉樹。這意味著除了最后一層，其他層都被完全填滿，且最后一層的節點都盡可能地靠左排列。

• 堆的數組表示：由于堆是完全二叉樹，可以用數組 heap[0…n-1] 來存儲（通常索引從 0 開始）：

  • 根節點：heap[0]
  • 節點 i 的左子節點：heap[2*i + 1]
  • 節點 i 的右子節點：heap[2*i + 2]
  • 節點 i 的父節點：heap[(i-1) / 2] (整數除法)

這種表示法非常節省空間，且父子節點的訪問是 O(1) 的。

        索引: 0 (值: 50)/                  \索引: 1 (值: 30)     索引: 2 (值: 40)/        \           /        \
索引:3    索引:4     索引:5     索引:6
(值:20)   (值:10)   (值:35)   (值:25)

數組索引:   0     1     2     3     4     5     6+-----+-----+-----+-----+-----+-----+-----+
數組值:   | 50  | 30  | 40  | 20  | 10  | 35  | 25  |+-----+-----+-----+-----+-----+-----+-----+

2.堆主要有兩種類型：

大根堆 (Max Heap)：對于樹中的任意節點，其值大于或等于其子節點的值。因此，根節點（堆頂）是整個堆中最大的元素。

實現大根堆：

package DiGui;public class Dui {public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}
}

大根堆應用: 去掉堆中的最大值，其結構仍保持大根堆

實現思路：
1.找到堆中最大值：肯定是數組中，下標為0的數，這個很簡單。
2.去掉最大值保持大根堆：將數組中下標最大的數，賦值給下標為0位置，在用heapify方法往下調整堆結構。

（heapify方法）：

//構建堆，index：構建堆結構下表，一下全是堆結構，heapSize：整個arr數組長度防止越界
public static void heapify(int [] arr. int index, int heapSize){//index 左孩子int left = index * 2 + 1;while (left < heapSize) {//index右孩子，與左孩子比較，取最大值下標int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;//判斷arr[largest] 與 arr[index] 大小取最大值下標largest = arr[largest] > arr[index] ? largest : index;if (largest == index) {break;}swap( arr, largest, index);index = largest;}
}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];

時間復雜度O(logN)

最小堆 (Min Heap)：對于樹中的任意節點，其值小于或等于其子節點的值。因此，根節點（堆頂）是整個堆中最小的元素。

堆排序

先來看代碼吧：

package DiGui;public class Dui {public static void heapSort(int [] arr) {if (arr == null || arr.length < 2) {return;}//先把整個數組變成大根堆for (int i = 0; i < arr.length; i++) {heapInsert(arr, i);}//再使整個大根堆有序int heapSize = arr.length;//將數組中最后一個數跟第一個數交換，再heapify，之后一個一個交換，使其完全有序swap(arr, 0, --heapSize);while (heapSize > 0) {heapify(arr, 0, heapSize);swap(arr, 0, --heapSize);}}//public static void heapInsert(int [] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;}}public static void heapify(int [] arr, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[largest] > arr[index] ? largest : index;if (largest == index) {break;}swap(arr, largest, index);index = largest;}}public static void swap(int [] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}
}

其實就是把上面兩個問題結合起來
時間復雜度O（N*logN）

小白啊！！！寫的不好輕噴啊🤯如果覺得寫的不好，點個贊吧🤪（批評是我寫作的動力）

…。。。。。。。。。。。…

…。。。。。。。。。。。…