C++学习记录算法篇-堆排序

一、堆

  • 堆是一颗完全二叉树
  • 如果堆的每一个节点（叶子节点除外）都大于他的子节点，这样的堆称为大根堆
  • 如果堆的每一个节点（叶子节点除外）都小于他的子节点，这样的堆称为小根堆
  • 对于用数组储存的堆，有以下运算性质：
    1. 某个节点i的父节点下标为：（i-1）/2 （整数除法）
    2. 某个节点i的左孩子节点下标为： i*2+1
    3. 某个节点i的右孩子节点下标为： i*2+2

二、堆排序（以从小到大为例）

利用堆的性质进行排序：从小到大使用大根堆，从大到小使用小根堆

大根堆的根节点的值最大，因此不断地把根节点放到数组的最末端，放完再维护堆，就可以实现从小到大排序

三、代码实现：

  1. 首先实现堆的维护：

    对于某个待维护的下标，我们要维护其子节点，子节点的子节点…直到叶子节点，这是一个递归的过程

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //维护堆的性质，以大根堆为例：
    //所需要的参数：数组，数组的长度，待维护的下标
    void heapify(int arr[], int n, int i)
    {
    	//定位待维护下标及其左右孩子，先默认最大值即为待维护节点
    	int largest = i;
    	int lson = i * 2 + 1;
    	int rson = i * 2 + 2;
    	
    	//下面是堆的维护
    	if (lson < n && arr[largest] < arr[lson])
    		largest = lson;
    	if (rson < n && arr[largest] < arr[rson])
    		largest = rson;
    	if (largest != i)
    	{
    		swap(arr[i], arr[largest]);
    		heapify(arr, n, largest);//递归维护
    	}

    	return;
    }

  2. 堆排序的入口：

    • 首先是建立堆，对于长度为n的数组，从（n-1-1）/2的下标开始往上维护
    • 建立完堆后，把堆顶和数组的最后一个元素交换。交换后堆需要再次维护，此时数组的长度-1
    • 依次类推，直到堆顶只剩下一个元素，最后将此元素排好。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    void heap_sort(int arr[], int n)
    {
    	//建堆
    	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    	{
    		heapify(arr, n, i);
    	}

    	//堆排序
    	for (int i = n - 1; i >= 0; i--)
    	{
    		swap(arr[i], arr[0]);
    		heapify(arr, i, 0);
    		//交换一次后，要再次维护堆使其再次变成大根堆，此时数组的长度-1，即长度为i
    	}
    	return;
    }

三、堆排序的时间复杂度为O（nlog2n【以2为底，n的对数】）

​ 空间复杂度为O（1），因为无需用到额外空间。

​ 堆排序是不稳定的