堆排序(C实现)

悠悠 2024-04-17 05:54 70阅读 0赞

# 堆排序 #

**目录**

堆的概念及结构   
堆的实现  
堆排序  
堆排序的特点  
堆排接口实现

--------------------

> ##  堆的概念及结构 : ##
> 
> 如果有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
> 
> 堆在逻辑上是一个完全二叉树的结构,在结构上是顺序表(数组)
> 
> 需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。  [内存中的堆区详解请点击][Link 1]
> 
> ![20190824223902823.gif][]     幸亏还有下面图解  
> **堆的性质：**  
> 堆中某个节点的值总是不大于或不小于其父节点的值( 一个堆要么是大跟对, 要么是小根堆 )  
> 堆总是一棵完全二叉树。

我们来看一个小根堆

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]

逻辑结构(完全二叉树)                                       存储结构(顺序)

--------------------

## 堆的实现 ##

要实现堆, 我们就必须先知道向下调整算法

> ###     堆向下调整算法: ###
> 
> 现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆(或大堆)。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]

> ### 堆的创建 ###
> 
> 我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过向下调整算法，把它构建成一个堆。但这颗完全二叉树根节点左右子树不是堆，我们怎么调整呢？
> 
> 这里我们从倒数的第一个非叶子节点开始依次向上对每个节点执行向下调整算法，一直调整到根节点，就可以调整成一个堆。

如图 : 数组1 3 4 5 7 2 6 8 0 , 最后一个非叶子节点为5,  从5开始向上依次对每个结点执行向下调整算法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2][]

数组5 2 0 1 3 1 4  ![20190824221806124.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3][]

**节点数 : size  
最后一个非叶子节点下标 : size / 2 - 1 ;**

堆的创建(数组->堆)代码实现 :

for (int i = size / 2 - 1; i >= 0; --i) {//将数组变成堆
    	adjustDown(array, i, size);//向下调整算法
    }

### 堆的插入 ###

> 先将新的数据插到完全二叉树的尾巴上, 再从最后一个非叶子节点依次向上开始对每一个节点执行向下执行算法, 直到根节点执行完结束

**图解 : **

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 4][]

### 堆的删除 ###

> 删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法(从根节点向下)。

**图解 :**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 5][]

**代码实现:**

void HeapPop(HPDataType* array,int* size) {
    	if (size == 0) {
    		return;
    	}
    	--*size;
    	int tmp = array[0];
    	array[0] = array[*size];
    	array[*size] = tmp;
    	adjustDown(array, 0,*size);
    }

## 堆排序 ##

> 堆排序的步骤 : (升序构建大根堆, 降序构建小根堆, 下面以升序为例)
> 
> 1. 先进行堆的创建( 将一个数组变成一个大根堆 )
> 
> 2. 再将堆顶根节点和最后一个节点交换 , 这时 , 最大值已经是最后一个节点 , 剩余待排序节点数为  n - 1
> 
> 3. 将剩余的 n - 1个节点的完全二叉树再构建成一个大根堆 ,也就是重复步骤1 , 2 ,如此反复

图解 :

以数组    ![20190824234152615.png][] 为例

![2019082423435325.png][]![20190824234407340.png][]灰色代表要交换, ![201908242344273.png][]绿色代表从根节点执行向下调整算法,![20190824234532787.png][]蓝色代表已排序完成

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 8][]

### 堆排序的特点 ###

> 稳定性 :不稳定
> 
> 时间复杂度 :O(N\*logN)
> 
> 空间复杂度 : O(N\*logN)

### 堆排接口实现 ###

hpsort.h声明

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    typedef int HPDataType;
    void adjustDown(HPDataType* array, int n, int size);
    void HeapPop(HPDataType* array, int size);
    void HeapSort(HPDataType* array, int size);

hpsort.c进行定义

#include"hpsort.h"
    void adjustDown(HPDataType* array, int n, int size) {//向下调整算法
    	int cur = n;
    	int tmp;
    	while (cur * 2 + 1 < size) {//循环直到左孩子不存在
    		if (cur * 2 + 2 >= size) {
    			n = cur * 2 + 1;//没有右孩子, 只能是左孩子
    		}
    		else if (array[cur * 2 + 1] > array[cur * 2 + 2]) {
    			n = cur * 2 + 1;
    		}
    		else {
    			n = cur * 2 + 2;
    		}
     
    		if (array[cur] < array[n]) {
    			tmp = array[cur];
    			array[cur] = array[n];
    			array[n] = tmp;
    			cur = n;
    		}
    		else {
    			break;
    		}
    	}
    }
    void HeapPop(HPDataType* array,int* size) {
    	if (size == 0) {
    		return;
    	}
    	--*size;
    	int tmp = array[0];
    	array[0] = array[*size];
    	array[*size] = tmp;
    	adjustDown(array, 0,*size);
    }
    void HeapSort(HPDataType* array, int size) {
    	for (int i = size / 2 - 1; i >= 0; --i) {//将数组变成堆
    		adjustDown(array, i, size);
    	}
     
    	int tmp = size;
    	while (size > 1) {//排序
    		HeapPop(array,&size);
    	}
    	size = tmp;
    }

main.c 实现调试入口

#include"heap.h"
     
    int main() {
    	int date[10] = { 29,72,48,53,45,30,18,36,15,35};
    	Heap hp;
    	HeapInit(&hp, date, 10);
    	HeapPrint_(&hp);
    	putchar('\n');
    	HeapPrint(&hp);
    	putchar('\n');	
    	putchar('\n');
     
     
    	HeapPush(&hp, 10);
    	HeapPrint_(&hp);
    	putchar('\n');
    	HeapPrint(&hp);
    	putchar('\n');
    	putchar('\n');
     
    	HeapPop(&hp);
    	HeapPrint_(&hp);
    	putchar('\n');
    	HeapPrint(&hp);
    	putchar('\n');
    	putchar('\n');
     
     
    	HeapSort(&hp);
    	HeapPrint_(&hp);
    	putchar('\n');
    	HeapPrint(&hp);
    	system("pause");
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41071068/article/details/90758502#4.%E5%A0%86%E5%8C%BA
[20190824223902823.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6f6ffa439e8b464b912072f1b5d7fc0d.gif
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ceb49be49300400da7ba545574232fc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/b8047abfea71432ab37d7e4e3549a80a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/f26a2c67b3cb4deeb941c817111eca24.png
[20190824221806124.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6f7e2dc70d494b42bee9700d875de86a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/d6ff41bc057e44ca8dbdef054eed3e9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/3461fcfd98ea4c8991a96e2d489edcef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/5796ebfe0ca94bddbcc166ecf0b4c001.png
[20190824234152615.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/a34571959e1d496e9037b31e6a89c425.png
[2019082423435325.png]: https://img-blog.csdnimg.cn/2019082423435325.png
[20190824234407340.png]: https://img-blog.csdnimg.cn/20190824234407340.png
[201908242344273.png]: https://img-blog.csdnimg.cn/201908242344273.png
[20190824234532787.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/29a615b00555434c9ebfa11543f7f25c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/8503a727aefb4478a8a8486147e69ad6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/df57bf383a0e4cd19077b69c119fdd3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/ca68bf5261c94cf5a647fe31e6ed27fd.png