【数据结构】堆：堆的构建，堆的向上调整算法，堆的向下调整算法、堆排序

目录

一、堆的定义

1、堆的定义：

2、根节点与其左、右孩子间的联系

??二、堆的创建

1、堆的向下调整算法?

2、堆的向上调整算法?

三、堆排序

---

一、堆的定义

1、堆的定义：

堆可以被看作是一棵完全二叉树的数组对象。即在存储结构上是数组，在逻辑结构上是一棵完全二叉树。在堆中，树的每个节点都满足堆属性，即父节点的值大于（或小于）其子节点的值。

具体而言，对于最大堆，父节点的值大于等于其子节点的值；而对于最小堆，则是父节点的值小于等于其子节点的值。这使得堆的根节点（常常是数组的第一个元素）成为堆中最大（或最小）的元素。

---

2、根节点与其左、右孩子间的联系

在堆中，根节点和其子节点之间存在一种特殊的联系。

????????对于任意一个节点 i，其左子节点位于位置 2i+1，右子节点位于位置 2i+2。反之，对于任意一个节点 j，其父节点位于位置 (j-1)/2。（这里的位置是指在数组中的索引位置）

????????换句话说，如果我们将堆表示为一个数组，那么对于任意节点 i，其左子节点就是数组中下标为 2i+1 的元素，右子节点就是数组中下标为 2i+2 的元素。而节点 i 的父节点就是数组中下标为 (i-1)/2 的元素。

---

二、堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们介绍两种方法：堆的向下调整算法和堆的向上调整算法

1、堆的向下调整算法?

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

具体步骤如下：

1. 首先，根据二叉树的性质，最后一个非叶子节点的索引可以通过?(n-2)/2?计算得到，其中?n?是二叉树的节点总数。

2. 我们可以使用一个循环，从最后一个非叶子节点开始，依次向前遍历每个节点。

3. 对于每个节点，我们可以调用?AdjustDown?函数来对其进行向下调整的操作。

4. 通过依次向上调整每个节点，我们可以确保整个二叉树满足堆的性质。

?

代码及注释：??

#include <stdio.h>
#include<stdlib.h>

void swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void AdjustDown(int* a, int n, int root)
{
    int child; // 子节点的索引
    child = root * 2 + 1; // 计算左孩子节点的索引
    while (child < n) // 当存在孩子节点时循环
    {
        if (child + 1 < n && a[child + 1] > a[child]) // 如果存在右孩子且右孩子大于左孩子
        {
            child++; // 将 child 置为右孩子的索引
        }
        if (a[root] < a[child]) // 如果根节点小于孩子节点
        {
            swap(&a[root], &a[child]); // 交换根节点和孩子节点的值
        }
        root = child; // 将根节点更新为孩子节点
        child = root * 2 + 1; // 计算新根节点的左孩子节点索引
    }
}

int main()
{
	int a[] = {10,1,3,2,4,6,8,9,7};
	int n = sizeof(a) / sizeof(int);
    int root = (n - 2) / 2;
    int i;
    for (i = root; i >= 0; i--)
    {
        AdjustDown(a, n, i); // 对每个根节点进行向下调整操作
    }

	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

---

2、堆的向上调整算法?

• 开始时，我们将数组第一个元素视为一个堆。
• 对于后续每个元素，调用?AdjustUp?函数进行向上调整的操作，使当前包含的数组元素满足堆的性质——即向堆中插入数据并通过向上调整使其成为新的堆。
• AdjustUp?函数比较元素的值与其父节点的值，如果子节点的值大于父节点的值，则交换两个节点的值，并把?child?更新为其父节点的索引，继续向上比较。
• 这样循环调整每个元素，可以使整个数组满足堆的性质。
• 

代码及注释：??

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int HPDataType;

#include <stdio.h>
#include <assert.h>

// 交换两个元素的值
void Swap(int* a, int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 向上调整操作
void AdjustUp(int* a, int child)
{
    assert(a);
    int parent;
    while (child > 0)
    {
        parent = (child - 1) / 2;  // 计算父节点位置
        if (a[child] > a[parent])  // 如果子节点的值大于父节点的值
        {
            Swap(&a[child], &a[parent]);  // 交换两个节点的值
            child = parent;  // child 更新为 parent，继续向上比较
        }
        else
        {
            break;
        }
    }
}

int main()
{
    int a[] = {10, 1, 3, 2, 4, 6, 8, 9, 7};
    int n = sizeof(a) / sizeof(int);
    int i;

    for (i = 0; i < n; i++)
    {
        AdjustUp(a, i);  // 对每个节点进行向上调整操作
    }

    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);  // 输出调整后的数组
    }
    
    return 0;
}

---

三、堆排序

堆排序是一种基于二叉堆（heap）数据结构的排序算法。它的思想可以概括为以下几个步骤：

1. 构建堆：将待排序的数组视为一个完全二叉树，并将其转化为一个堆。这可通过从最后一个非叶子节点开始，逐个向上调整每个节点来完成。调整操作会使得当前节点和其子树满足堆的性质，即父节点的值大于等于（或小于等于）其子节点的值。这样就构建了一个最大堆（或最小堆）。

2. 排序：经过构建堆操作后，堆顶元素是最大（或最小）的元素。我们可以将堆顶元素与堆中最后一个元素交换位置，然后将堆的大小减小 1。这样，最大（或最小）的元素会被放置到正确的位置（即最后一个位置）。接着，我们对堆顶元素进行向下调整，使得堆再次满足堆的性质。重复以上步骤，直到堆中只剩下一个元素。

3. 返回有序序列：当堆中只剩下一个元素时，所有的元素都已经交换并放置到了正确的位置。此时，我们就得到了一个有序的序列。

堆排序的时间复杂度为 O(nlogn)，其中 n 是数组的大小。它是一种原址排序算法，因为它只需要用到原始数组，不需要使用额外的空间。同时，堆排序也是一种稳定的排序算法。

代码及注释：?

void AdjustDown(int* a, int parent, int n)
{
    // 计算左子节点的索引
    int child = parent * 2 + 1;
    
    // 当左子节点在数组范围内时进行循环
    while (child < n)
    {
        // 如果右子节点存在且比左子节点大，则选择右子节点作为与父节点进行比较的子节点
        if (child + 1 < n && a[child] < a[child + 1]) 
        {
            child++;
        }
        
        // 如果父节点小于子节点，则交换它们的值
        if (a[parent] < a[child]) 
        {
            swap(&a[parent], &a[child]);
            // 更新父节点和子节点的索引
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int* a, int n)
{
    // 从最后一个非叶子节点开始，依次调用 AdjustDown 函数，构建最大堆
    int i = 0;
    int end = n / 2 - 1;
    for (i = end; i >= 0; i--)
    {
        AdjustDown(a, i, n);
    }
    
    // 交换堆顶元素与最后一个元素，并向下调整堆
    for (i = 0; i < n; i++)
    {
        swap(&a[0], &a[n - i - 1]);
        AdjustDown(a, 0, n - i - 1);
    }
}

?