堆

完全二叉树

完全二叉树

• h-1 层全满
• h 层从左排
  完全二叉树可以使用顺序链表(数组)来存储.

堆

1. 大根堆:所有子树的父节点不小于它的孩子
2. 小根堆:所有子树的父节点不大于它的孩子

堆排序

主要介绍升序法, 使用大根堆

1. 子树调整为堆
2. 构建堆
3. 排序

子树调整为堆

void adjustup(int* heap, int i, int n)
{  // 使以i为根的子树是大根堆
    int index;
    while (i <= n / 2 - 1)  //非叶子节点
    {
        index = i * 2;
        if (index + 1 < n && bt[index + 1] > bt[index])  //不存在右节点
            index++;
        if (heap[i] < heap[index])
        {  //将大数放在父节点
            int temp = heap[i];
            heap[i] = heap[index];
            heap[index] = temp;
            i = index;  //调整后的子树需要重新调整
        }
        else
            break;
    }
}

构建堆

void heapbuild(int* heap, int n)
{ // 从下向上构建
    for (int i = n / 2 - 1; i >= 0; i--)
        adjustup(heap, i, n);
}

排序

void heap_sort(int* heap, int n)
{
    heapbuild(heap, n);  // 构建大根堆
    while (n > 1)
    {
        int temp = heap[0];     //将最大的
        heap[0] = heap[n - 1];  //根结点移
        heap[n - 1] = temp;     //到最后
        n--;
        heapbuild(heap, n);
    }
}