堆排序向上调整完整代码
时间: 2024-05-25 21:09:08 浏览: 12
堆排序是一种利用堆的数据结构进行排序的算法,其中向上调整是堆排序中的重要操作。以下是向上调整的完整代码:
```
void heapAdjust(int* arr, int i, int length) {
int temp = arr[i];
int j = 2 * i + 1;
while (j < length) {
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (arr[j] > temp) {
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
}
else {
break;
}
}
arr[i] = temp;
}
```
其中,arr表示待排序的数组,i表示需要调整的节点下标,length表示数组的长度。该函数将第i个节点向上调整至合适位置。在该函数中,首先将第i个节点的值存储在temp中,并将j初始化为其左子节点的下标(即2*i+1)。然后,如果其右子节点比左子节点大,则将j更新为右子节点的下标。接着,如果子节点中最大的值比temp大,则将该子节点的值赋给其父节点,并将i更新为该子节点的下标,再继续向下遍历。最后,将temp赋给最后一个被修改的节点,以完成向上调整操作。
相关问题
堆排序向下和向上调整
堆排序是一种基于堆数据结构的排序算法,其中包括向下调整和向上调整两个关键步骤。
1. 向下调整(AdjustDown):在堆排序中,向下调整用于将一个元素下沉到合适的位置,以维持堆的性质。具体步骤如下:
- 首先,将当前节点标记为根节点。
- 比较根节点与其左右子节点的值,找到最大(或最小)的节点。
- 如果根节点的值小于(或大于)最大(或最小)的子节点的值,则交换根节点与最大(或最小)子节点的值。
- 将当前节点更新为最大(或最小)子节点的位置,并重复上述步骤,直到当前节点不再有子节点或满足堆的性质。
2. 向上调整(AdjustUp):在堆排序中,向上调整用于将一个元素上浮到合适的位置,以维持堆的性质。具体步骤如下:
- 首先,将当前节点标记为叶子节点。
- 比较叶子节点与其父节点的值,如果叶子节点的值大于(或小于)父节点的值,则交换叶子节点与父节点的值。
- 将当前节点更新为父节点的位置,并重复上述步骤,直到当前节点不再有父节点或满足堆的性质。
以下是一个示例代码,演示了堆排序中的向下调整和向上调整的过程:
```python
def adjust_down(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
adjust_down(arr, n, largest)
def adjust_up(arr, i):
parent = (i - 1) // 2
if parent >= 0 and arr[parent] < arr[i]:
arr[parent], arr[i] = arr[i], arr[parent]
adjust_up(arr, parent)
# 示例数据
arr = [4, 10, 3, 5, 1]
n = len(arr)
# 向下调整示例
adjust_down(arr, n, 0)
print("向下调整后的结果:", arr) # 输出:[10, 5, 3, 4, 1]
# 向上调整示例
arr.append(7)
n += 1
adjust_up(arr, n-1)
print("向上调整后的结果:", arr) # 输出:[10, 7, 3, 5, 1, 4]
```
用c语言写一个堆排序代码
### 回答1:
#include<stdio.h>
int main()
{
int n, temp;
printf("输入数组大小: ");
scanf("%d", &n);
int arr[n];
printf("输入 %d 个数: \n", n);
for(int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
// 堆排序
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
// 将根节点和最后一个节点交换
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新 heapify 根节点
heapify(arr, i, 0);
}
// 打印排序结果
printf("排序结果: \n");
for (int i=0; i<n; ++i)
printf("%d ",arr[i]);
return 0;
} // 堆排序算法
void heapify(int arr[], int n, int i)
{
int largest = i; // 初始化最大值为根
int l = 2*i + 1; // 左子节点
int r = 2*i + 2; // 右子节点
// 如果左子节点大于根
if (l < n && arr[l] > arr[largest])
largest = l;
// 如果右子节点大于最大值
if (r < n && arr[r] > arr[largest])
largest = r;
// 如果最大值不是根节点
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调用调整子节点
heapify(arr, n, largest);
}
}
### 回答2:
堆排序是一种基于二叉堆的排序算法,使用数组来实现堆的操作。下面是一个用C语言实现堆排序的代码:
```c
#include <stdio.h>
// 交换两个元素的位置
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 调整堆使其满足堆的性质
void heapify(int arr[], int n, int i) {
int largest = i; // 将当前节点设为最大值
int left = 2 * i + 1; // 左子节点的索引
int right = 2 * i + 2; // 右子节点的索引
// 如果左子节点大于根节点,更新最大值的索引
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点大于根节点,更新最大值的索引
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值的索引发生变化,交换节点,并递归调整子堆
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(int arr[], int n) {
// 构建最大堆,自底向上调整堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次将最大值放到数组末尾,并调整堆
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
// 打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:");
printArray(arr, n);
heapSort(arr, n);
printf("排序结果:");
printArray(arr, n);
return 0;
}
```
这个代码实现了使用堆排序算法对一个整型数组进行排序。首先,使用`heapify`函数将数组转换为最大堆;然后,利用`heapSort`函数将最大值逐个放到数组末尾并调整堆,最终得到排序结果。运行该程序,输出结果为:
```
原始数组:12 11 13 5 6 7
排序结果:5 6 7 11 12 13
```
这就是堆排序的实现代码。
### 回答3:
下面是使用C语言编写的堆排序代码:
```c
#include <stdio.h>
// 调整堆,使其成为最大堆
void maxHeapify(int arr[], int n, int i) {
int largest = i; // 初始化最大元素为根节点
int left = 2 * i + 1; // 左子节点的索引
int right = 2 * i + 2; // 右子节点的索引
// 如果左子节点大于根节点,将最大元素索引更新为左子节点
if (left < n && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于根节点,将最大元素索引更新为右子节点
if (right < n && arr[right] > arr[largest])
largest = right;
// 如果最大元素不是根节点,交换根节点和最大元素
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 继续向下调整交换后的节点
maxHeapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(int arr[], int n) {
// 构建最大堆,从最后一个非叶子节点向上调整
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
// 依次取出最大元素并调整堆
for (int i = n - 1; i > 0; i--) {
// 将根节点(最大元素)与最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆,使其重新成为最大堆
maxHeapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
heapSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
该代码实现了堆排序的功能。其中,`maxHeapify`函数用于调整堆,使其成为最大堆;`heapSort`函数用于对数组进行堆排序。在`main`函数中,我们传入一个数组,并对其进行堆排序操作。最终输出排序后的数组。