堆排序的排序思想？

堆排序是一种高效的排序算法，其基本思想是利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树，通常用数组来表示。堆排序的基本步骤如下：

1. 构建初始堆：

• 将待排序的数组转换成一个最大堆（或最小堆）。在最大堆中，父节点的值总是大于或等于其子节点的值。转换过程从最后一个非叶子节点开始，向上调整堆，确保堆的性质。

2. 堆排序过程：

• 将堆顶元素（最大值或最小值）与最后一个元素交换，然后将剩余的元素重新调整为堆。
• 重复上述过程，每次将堆顶元素与当前未排序部分的最后一个元素交换，并重新调整堆，直到整个数组被排序。

3. 调整堆：

• 每次交换后，需要调整堆以保持堆的性质。调整过程从交换后的堆顶元素开始，向下调整，确保每个节点都满足堆的性质。

4. 循环结束：

• 当所有元素都通过堆调整并交换到数组的前部时，排序完成。

具体步骤：

1. 假设数组长度为n，初始时数组为A[1…n]。
2. 将数组从后向前转换为最大堆：

• 从最后一个非叶子节点开始（即A[n/2]），向下调整堆。
• 每个节点向下调整时，比较其值与其子节点的值，如果当前节点的值小于其子节点的值，则与较大的子节点交换。
• 重复上述过程，直到堆顶元素满足最大堆的性质。

3. 将堆顶元素（最大值）与数组的最后一个元素交换，然后重新调整堆。
4. 重复上述过程，直到堆的大小减少到1。

时间复杂度：

• 堆排序的时间复杂度为O(n log n)，其中n是数组的长度。

空间复杂度：

• 堆排序是原地排序算法，不需要额外的存储空间，因此空间复杂度为O(1)。

稳定性：

• 堆排序不是稳定的排序算法，因为相同的元素在排序过程中可能会交换位置。

代码：

// 向下调整算法，使以 parent 为根节点的堆满足大根堆性质 void AdjustDown(int* a, int parent, int n) { 	assert(a); 	int child = parent * 2 + 1;  	// 确保子节点不超过堆的大小 	while (child < n) 	{ 		// 找到左右子节点中较大的一个 		if (child + 1 < n && a[child] < a[child + 1]) 		{ 			++child; 		}  		// 父节点小于较大子节点，交换父子节点位置 		if (a[child] > a[parent]) 		{ 			Swap(&a[child], &a[parent]); 			parent = child; 			child = parent * 2 + 1; 		} 		else 		{ 			break; // 父节点已经大于等于子节点，退出循环 		} 	} }  // 堆排序算法 void HeapSort(int* a, int n) { 	// 升序排序建大根堆，降序排序建小根堆 	for (int i = (n - 1) / 2; i >= 0; i--) // 从最后一个非叶子节点开始向下调整 	{ 		AdjustDown(a, i, n); // 向下调整以 i 为根节点的大根堆 	}  	int end = n - 1; 	while (end > 0) 	{ 		Swap(&a[0], &a[end]); // 将堆顶元素（即最大值）与堆末尾元素交换 		AdjustDown(a, 0, end); // 对新的堆顶进行向下调整，使其满足大根堆性质 		--end; // 堆大小减 1，排除已排序好的最大值 	} } 

使用 priority_queue 实现

逆序：

void heapSort(vector& nums) {     priority_queue maxHeap;      // 将数组元素插入最大堆中     for (int num : nums) {         maxHeap.push(num);     }      // 依次取出堆顶元素放入结果数组中（逆序）     for (int i = nums.size() - 1; i >= 0; --i) {         nums[i] = maxHeap.top();         maxHeap.pop();     } } 

顺序：

void heapSort(vector& nums) {     priority_queue, greater> minHeap;      // 将数组元素插入最小堆中     for (int num : nums) {         minHeap.push(num);     }      // 依次取出堆顶元素放入结果数组中（顺序）     for (int i = 0; i < nums.size(); ++i) {         nums[i] = minHeap.top();         minHeap.pop();     } }