当前位置：首页 > ops >正文

力扣 23 912题（堆）

ops 2025/9/2 11:30:53

排序数组

链接：https://leetcode.cn/problems/sort-an-array/

堆排序 模板题

code

void swap(int* nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;
}void heapinsert(int* nums, int i) {while(nums[i] > nums[(i - 1) / 2]) {swap(nums, i, (i - 1) / 2);i = (i - 1) / 2;}
}void heapify(int* nums, int i, int size) {int l = i * 2 + 1;while(l < size) {int best = l + 1 < size && nums[l + 1] > nums[l] ? l + 1 : l;best = nums[best] > nums[i] ? best : i;if(best == i) break;swap(nums, i, best);i = best;l = i * 2 + 1;}
}// 自顶向底
void heapsort1(int* nums, int n) {for (int i = 0; i < n; i++) {heapinsert(nums, i);}int size = n;while (size > 1) {swap(nums, 0, --size);heapify(nums, 0, size);}
}// 自底向顶
void heapsort2(int* nums, int n) {for (int i = n - 1; i >= 0; i--) {heapify(nums, i, n);}int size = n;while (size > 1) {swap(nums, 0, --size);heapify(nums, 0, size);}
}int* sortArray(int* nums, int numsSize, int* returnSize) {*returnSize = numsSize;int* result = (int*)malloc(numsSize * sizeof(int));memcpy(result, nums, sizeof(int) * numsSize);heapsort2(result, numsSize);return result;
}

合并 K 个升序链表

链接：https://leetcode.cn/problems/merge-k-sorted-lists/

小根堆 认为是优解（打败100%，其实模板还是一样的，中心就是两个函数）

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* heap[10001];
int heap_size;void swap(int i, int j) {struct ListNode* temp = heap[i];heap[i] = heap[j];heap[j] = temp;
}void heapInsert(struct ListNode* node) {if (node == NULL) return;heap[++heap_size] = node;int i = heap_size;while (i > 1 && heap[i]->val < heap[i>>1]->val) {swap(i, i>>1);i >>= 1;}
}void heapify(int i) {int l = i<<1;while(l <= heap_size) {int best = l + 1 <= heap_size && heap[l + 1]->val < heap[l]->val ? l + 1 : l;best = heap[best]->val < heap[i]->val ? best : i;if(best == i) break;swap(i, best);i = best;l = i<<1;}
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));    // 虚拟节点dummy->next = NULL;                                                           struct ListNode* rear = dummy;heap_size = 0;for (int i = 0; i < listsSize; i++) {if (lists[i] != NULL) {heapInsert(lists[i]);}}while (heap_size > 0) {struct ListNode* min_node = heap[1];rear->next = min_node;rear = rear->next;if (min_node->next != NULL) {heap[1] = heap[1]->next;heapify(1);} else {heap[1] = heap[heap_size--];if (heap_size > 0) {heapify(1);}}}rear->next = NULL; struct ListNode* result = dummy->next;free(dummy);return result;
}