标签：结点 int 堆排序 up down 算法 操作 数据结构 size

堆与堆排序

1 堆的概念

• 堆用于维护一个数集。
• 堆是一个完全二叉树
• 小根堆：每个结点都小于等于它的左右子结点（递归定义）
  • 推论：每个结点都是以其为根节点的子树的最小值

堆是一棵完全二叉树

2 堆的性质

• 完全二叉树的性质：

完全二叉树的性质

条件	编号(或数量)
完全二叉树的层数	\(\lceil\log_2n\rceil\)
完全二叉树根节点向下走到叶子结点的最大距离	\(\lfloor\log_2n\rfloor\)
最后一个非叶子结点（向下走到叶子结点最大距离为 1 的最后一个结点）	n/2
向下走到叶子结点最大距离为 2 的最后一个结点	n/4
向下走到叶子结点最大距离为 d 的最后一个结点	\(n/2^d\)
向下走到叶子结点最大距离为 d 的结点个数	\(n/2^{d+1}-n/2^d=\)n/2^{d+1}$

• 小根堆的性质：由小根堆的定义可得每个结点都是以其为根节点的子树的最小值

这也是堆排序的思想，每一次将小根堆的根节点输出，然后维护剩下的节点作为一个小根堆。

3 堆的实现（小根堆为例）

• 使用一维数组来存储堆
  • 1 号点为根结点。
  • 结点 x 的左儿子是 2x ，右儿子是 2x+1
• 堆的基本操作：
  • down(x) 操作，将结点往下移动来维护一个小根堆
    1. 结点 i 与其左右孩子 2i 和 2i+1 比较，如果结点 i 不是三者之中的最小值，则结点 i 要向下移动。
    2. 结点 i 与其最小的孩子 t 交换位置后，然后递归 down(t)
  • up(x) 操作，把一个结点向上移动来维护一个小根堆
    1. 结点 i 与它的父节点 i/2 比较，如果父结点大于子结点，就将结点 i 与 i/2 交换
    2. i /= 2 直到父结点小于子结点

down 操作

/// down 操作
void down(int h[], int size, int i)
{
    int t = i;
    if(2 * i <= size && h[i] > h[2 * i]) t = 2 * i;
    if(2 * i + 1 <= size && h[t] > h[2 * i + 1]) t = 2 * i + 1;
    if(t != i)
    {
        int temp = h[i];
        h[i] = h[t];
        h[t] = temp;
        down(h, size, t);
    }
}

up操作

/// up 操作
void up(int h[], int size, int i)
{
    while(i / 2 && h[i / 2] > h[i])
    {
        int temp = h[i];
        h[i] = h[i / 2];
        h[i / 2] = temp;
        i /= 2;
    }
}

• 使用基本操作 up 和 down 就可以完成如下操作：

/// - 插入操作
/// 新增元素插在末尾，然后对他进行 up 操作
heap[++ size] = x;up(size);

/// - 最小值
/// 根节点即为最小值
heap[1];

/// - 删除最小值
/// 用堆的最后一个元素覆盖根节点，然后堆的尺寸减 1
/// 然后对根节点执行 down 操作
heap[1] = heap[size];size--;
down(1);

/// - 删除任意一个元素
/// 用堆的最后一个元素覆盖要删除的元素，然后堆的尺寸减 1
/// 然后对覆盖后的结点执行 down 操作
heap[k] = heap[size];size--;
down(k);up(k);

/// - 修改一个元素的值
/// 修改结点元素值后，对其执行 down 操作或 up 操作
/// 这里减少了一个判断，down() 和 up() 都写上，只会执行其中一个。
heap[k] = x;down(x);up(x);

4 堆排序

• 推排序用于对一维数组的元素进行排序

1. down 操作将一维数组转换为小根堆：
   • down 只对非叶子结点操作才有意义，由完全二叉树的性质，最后一个非叶子结点的编号为 n / 2
   • 因此，从 i = n/2 到 i = 0 的结点进行 down 操作，这样就能得到小根堆。

for(int i = size / 2; i; i--) down(i);

2. 输出最小值，然后删除最小值，循环。

while(size)
{
    printf("%d ", h[1]);
    h[1] = h[size]; size--;
    down(1);
}

• 堆排序实现

void heap_sort(int h[], int size)
{
    for(int i = size / 2; i; i--) down(i);
    
    while(size)
	{
        printf("%d ", h[1]);
        h[1] = h[size]; size--;
        down(h, size, 1);
	}
}

• 堆排序时间复杂度：
  • 从 i=n/2 开始每次 i-- 遍历，对每个结点执行 down(i) 操作
  • 最坏的情况下，由前面提到的完全二叉树的性质，n 个结点中有 \(n/2^{d+1}\) 个结点向下走到叶子结点最大距离为 d ，这些结点每个要执行 d 次 down 操作。因此总共的算法时间复杂度为：

\[T(n)=\sum_{d=1}^{\lfloor\log_2n\rfloor}\frac{n}{2^{d+1}}d \]

由上式，可推得(推导过程后面再补)堆排序算法复杂度为 \(O(1)\)

标签：结点,int,堆排序,up,down,算法,操作,数据结构,size
From： https://www.cnblogs.com/Critical-Thinking/p/17238204.html