設計一個算法，找出數組中最小的k個數。以任意順序返回這k個數均可。

示例：

輸入： arr = [1,3,5,7,2,4,6,8], k = 4 輸出： [1,2,3,4]

比較替換堆頂的數時，不需要讓堆頂與數組的每一個數再進行比較，比較數組減去k個數之后剩下的數就行。

1.堆排序方法

// 選出最小的K個數，要建一個大堆// 大堆的向下調整算法
void HeapDown(int* heap, int k, int parent) {// 1.根據父親結點得到左孩子節點下標childint child = parent * 2 + 1;// 2.進入while循環進行向下調整（while的循環條件是child<k)while (child < k) {// 2.1比較左孩子和右孩子的值，如果右孩子更大，child++，注意要避免越界child+1<kif (child + 1 < k && heap[child] < heap[child + 1]) {child++;}// 2.2如果父親結點的值小于孩子結點，進行交換，交換后將child結點的下標賦值給父親結點，//    根據此時的父親結點計算下一個child的下標if (heap[parent] < heap[child]) {int temp = heap[parent];heap[parent] = heap[child];heap[child] = temp;parent = child;child = parent * 2 + 1;}// 2.3如果父親結點的值已經大于孩子結點，說明不需要再調整，break跳出循環elsebreak;}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize) {// 0.首先處理兩種特殊情況K<=0,K>=arrSzieif (k <= 0) {*returnSize = 0;return NULL;}if (k >= arrSize) {int* result = (int*)malloc(sizeof(int) * arrSize);memcpy(result, arr, sizeof(int) * arrSize);*returnSize = arrSize;return result;}// 1.首先開辟一個空間存我們新建的大堆數據int* heap = (int*)malloc(sizeof(int) * arrSize);// 2.將傳入的數組的數據memcpy到我們新建的空間memcpy(heap, arr, sizeof(int) * arrSize);// 3.從下往上進行向下調整構建大堆for (int i = (arrSize - 1 - 1) / 2; i >= 0; i--) {HeapDown(heap, arrSize, i);}int end = arrSize - 1;while (end > 0) {int tem = heap[0];heap[0] = heap[end];heap[end] = tem;end--;HeapDown(heap, end, 0);}int* arrtemp = (int*)malloc(sizeof(int) * k);memcpy(arrtemp, heap, sizeof(int) * k);*returnSize = k;return arrtemp;
}

1. 邊界條件的嚴謹性
   代碼開頭對k的特殊情況（k<=0和k>=數組長度）做了單獨處理：

   • 當k<=0時，返回空數組并設置returnSize=0；
   • 當k大于等于數組長度時，直接返回原數組。
     這種處理避免了后續無效的堆操作，也防止了數組訪問越界，體現了對 “異常輸入” 的考慮，是健壯性代碼的常見做法。

2. 堆操作的標準化實現

   • 向下調整算法（HeapDown）：這是堆操作的核心，代碼正確實現了大堆的向下調整邏輯：
     ① 先比較左右孩子，選擇更大的子節點（保證大堆特性）；
     ② 若父節點小于子節點，則交換兩者，并繼續向下調整；
     ③ 若父節點已大于子節點，說明堆已平衡，直接退出。
     其中對child+1 < k的越界檢查（避免右孩子不存在時的訪問錯誤），體現了細節處理的嚴謹性。

   • 堆的構建方式：從最后一個非葉子節點（(arrSize-1-1)/2）開始，向上依次調用HeapDown，這是構建堆的標準高效方法（時間復雜度O(n)），比從根節點逐個插入（O(n log n)）更優。

3. 接口設計的規范性
   函數通過returnSize參數返回結果數組的長度，符合 C 語言中 “動態數組需明確長度” 的設計習慣（調用者可通過returnSize正確遍歷結果），避免了因長度未知導致的越界訪問。

最優解：

// 選出最小的K個數，要建一個大堆// 大堆的向下調整算法
void HeapDown(int* heap, int k, int parent) {// 1.根據父親結點得到左孩子節點下標childint child = parent * 2 + 1;// 2.進入while循環進行向下調整（while的循環條件是child<k)while (child < k) {// 2.1比較左孩子和右孩子的值，如果右孩子更大，child++，注意要避免越界child+1<kif (child + 1 < k && heap[child] < heap[child + 1]) {child++;}// 2.2如果父親結點的值小于孩子結點，進行交換，交換后將child結點的下標賦值給父親結點，//    根據此時的父親結點計算下一個child的下標if (heap[parent] < heap[child]) {int temp = heap[parent];heap[parent] = heap[child];heap[child] = temp;parent = child;child = parent * 2 + 1;}// 2.3如果父親結點的值已經大于孩子結點，說明不需要再調整，break跳出循環elsebreak;}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize) {// 0.首先處理兩種特殊情況K<=0,K>=arrSzieif (k <= 0) {*returnSize = 0;return NULL;}if (k >= arrSize) {int* result = (int*)malloc(sizeof(int) * arrSize);memcpy(result, arr, sizeof(int) * arrSize);*returnSize = arrSize;return result;}// 1.首先開辟一個空間存我們新建的大堆數據int* heap = (int*)malloc(sizeof(int) * k);// 2.將傳入的數組的數據memcpy到我們新建的空間memcpy(heap, arr, sizeof(int) * k);// 3.從下往上進行向下調整構建大堆for (int i = (k - 1 - 1) / 2; i >= 0; i--) {HeapDown(heap, k, i);}// 4.將新建大堆的堆頂值與傳入數組剩下的arrSize-k個數據進行比較，如果堆頂的數更大，替換堆頂的數并進行向下調整//j從k開始即可for (int j = k; j < arrSize; j++) {if (heap[0] > arr[j]) {//直接替換即可heap[0]=arr[j];HeapDown(heap, k, 0);}}*returnSize = k;return heap;
}

1. 大堆的精準應用
   選出 “最小的 K 個數” 時，使用 “大堆” 是非常巧妙的選擇：

   • 大堆的堆頂始終是當前 K 個元素中的最大值，便于快速判斷新元素是否有資格進入 “最小 K 個” 的集合（只需比較新元素與堆頂）。
   • 若新元素更小，則替換堆頂并調整，保證堆中始終是當前最小的 K 個元素。
     這種思路體現了 “用合適的數據結構解決特定問題” 的設計思想。

2. 堆構建的高效實現

   • 構建堆時，從最后一個非葉子節點（(k-1-1)/2）開始向上調用HeapDown，這是堆初始化的標準高效方法（時間復雜度O(k)），而非從根節點逐個插入（O(k log k)）。
   • HeapDown函數的實現嚴謹：先比較左右孩子取較大值，再與父節點比較交換，確保大堆特性，且對右孩子的越界檢查（child+1 < k）避免了數組訪問錯誤。

3. 內存使用的合理性

   • 堆空間直接分配為k大小（malloc(sizeof(int)*k)），精準匹配需求，不浪費內存。
   • 最終直接返回堆空間作為結果，避免了額外的內存拷貝（上一版中arrtemp的拷貝操作）。