C语言顺序结构的二叉树之堆排序
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>一、堆</li><ul class="second_class_ul"><li>1. 概念与分类</li><li>2. 结构与性质</li><li>3. 入堆</li><li>4. 出堆</li></ul><li>二、堆排序</li><ul class="second_class_ul"></ul><li>三、堆排序的应用——TOP-K问题</li><ul class="second_class_ul"></ul><li>总结</li><ul class="second_class_ul"></ul></ul></div><p class="maodian"></p><h2>一、堆</h2><p class="maodian"></p><h3>1. 概念与分类</h3>
<p>上一期我们提到，二叉树的实现既可以用顺序结构，也可以用链式结构。本篇我们来学习<strong>顺序结构的二叉树，起个新名字——堆</strong>（heap）。<br />堆是完全二叉树，它的底层是顺序结构的数组，具有二叉树特性的同时，还有一些其他性质：</p>
<p>堆分为大堆和小堆（或称为大根堆、小根堆）：</p>
<ul><li><strong>大堆：大堆的每个结点的存储值都 >= 它的子结点的存储值。</strong></li><li><strong>小堆：小堆的每个结点的存储值都 <= 它的子结点的存储值。</strong></li></ul>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245054.png" /></p>
<p>譬如，在一个大堆中，某一个父结点的值为20，则它的子结点的值一定<=20；在一个小堆中，某一个父结点的值为20，则它的子结点的值一定>=20。</p>
<p>左孩子和右孩子的值的大小关系不确定。</p>
<p>换句话说，<strong>一个堆一定是大堆或小堆</strong>。以下的二叉树，既不是大堆也不是小堆，它们就不是堆：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245039.png" /></p>
<p class="maodian"></p><h3>2. 结构与性质</h3>
<p>定义数据结构堆：</p>
<div class="jb51code"><pre class="brush:cpp;">typedef struct Heap
{
HPDataType* arr;
int size;
int capacity;
}HP;
</pre></div>
<p>上面的画图是用逻辑结构表示堆，用存储结构表示堆就要用到数组了，牢记二叉树结点的编号方式：<strong>从上到下，从左到右</strong>：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245056.png" /></p>
<p>不难推断，堆的数组中有下列性质：</p>
<ul><li><strong>大堆的首元素（根结点）是整个堆的最大值，小堆的首元素（根结点）是整个堆的最小值。</strong></li><li><strong>若子结点的下标为i，则它的父结点是(i-1)/2。</strong></li><li><strong>若父结点的下标为i，则它的左孩子是2i+1，右孩子是2i+2。结点个数是n，2i+1 >= n 说明无左孩子，2i+2 >= n 说明无右孩子。</strong></li></ul>
<p>顺带给出堆的初始化和销毁方法，以及后面要用到的交换两个变量值的方法：</p>
<div class="jb51code"><pre class="brush:cpp;">void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPDestory(HP* php)
{
assert(php);
if (php->arr != NULL)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
</pre></div>
<p class="maodian"></p><h3>3. 入堆</h3>
<p>想要把一个新的数据插入堆，分为两步：</p>
<ol><li>把它插入堆数组末尾</li><li>仅仅插入数据后，可能会破坏堆的性质，所以还要进行“<strong>向上调整</strong>”操作：<strong>将新插入结点顺着其双亲往上调整位置至满足大堆或小堆的位置。</strong><br />我们以下面一个小堆为例，插入一个新数据10，如果它小于其父结点（不符合小堆），两者交换。再和新父结点比较，如果小于交换……直到满足小堆：<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245043.png" /></p></li></ol>
<p>所以，我们要知道<strong>向上调整算法</strong>：它有两个参数：要被调整的堆数组，要调整位置的结点的下标：</p>
<div class="jb51code"><pre class="brush:cpp;">void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2; //找这个结点的父结点
while (child > 0)
{
//调整的是小堆:<
//调整的是大堆:>
if (arr < arr)
{
Swap(&arr, &arr);
child = parent;
parent = (child - 1) / 2;
}
else //新数据已经到了对的位置
{
break;
}
}
}
</pre></div>
<p>这样，我们就能实现入堆操作了：</p>
<div class="jb51code"><pre class="brush:cpp;">void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity) //空间不够则需增容
{
int newcapacity = php->capacity == 0 ? 5 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->arr, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("relloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newcapacity;
}
php->arr = x; //新数据插到末尾，即下标为size的位置
AdjustUp(php->arr, php->size);
php->size++;
}
</pre></div>
<p>测试：</p>
<p>我们来实现一个小堆，乱序给一些数：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245015.png" /></p>
<p>将打印结果排列成堆的逻辑结构看看，发现确实是正确的小堆：</p>
<p class="maodian"></p><h3>4. 出堆</h3>
<p>我们所谓的出堆，出的并不是数组末尾数据，<strong>出的是第一个数据——堆的根结点</strong>。但是，直接除去数组首元素，再将后面元素的下标全体前挪，会使堆的所有结点位置关系“大乱套”，再想调整可就麻烦了。</p>
<p>因此，我们选择这样的出堆定元素方法：<strong>先将堆顶数据和堆的最后一个数据交换，size- -把数组末尾数据出掉，再对堆顶元素进行“向下调整”操作</strong>。相比刚才所有结点位置大乱套，这样只要调整一个结点的位置就好了。</p>
<p>向下调整算法和向上调整类似：它是比较结点和其较大或较小孩子的值，不断往下交换调整位置直至满足大堆或小堆：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245037.png" /></p>
<p>向下调整算法有三个参数：要被调整的堆数组、要调整的结点的下标、堆的数据个数</p>
<div class="jb51code"><pre class="brush:cpp;">void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = 2 * parent + 1;
while (child < n)
{
//调整的是小堆: >
//调整的是大堆: <
if (child + 1 < n && arr < arr) //找两个孩子中的较大/较小者
{
child++;
}
//调整的是小堆:<
//调整的是大堆:>
if (arr > arr)
{
Swap(&arr, &arr);
parent = child;
child = 2 * parent + 1;
}
else //调整完成
{
break;
}
}
}
</pre></div>
<p>这样，我们就能实现出堆操作了：</p>
<div class="jb51code"><pre class="brush:cpp;">void HPPop(HP* php)
{
assert(php);
assert(php->size != 0); //堆不能为空，否则无数据可出
Swap(&php->arr, &php->arr); //交换堆顶和堆尾数据
php->size--; //将堆尾数据出掉
AdjustDown(php->arr, 0, php->size);
}
</pre></div>
<p>测试：</p>
<p>我们来实现一个大堆，乱序给一些数，再进行一次出堆：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245050.png" /></p>
<p>分析逻辑结构，可以看到大堆实现成功，出堆也没有问题：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245012.png" /></p>
<p class="maodian"></p><h2>二、堆排序</h2>
<p>堆排序是一种排序方法，不是借助堆的数据结构，而是利用堆的思想进行排序：</p>
<p><strong>一个n个元素的数组，假如想排升序，就将数组建成一个大堆，堆顶是最大值，将堆顶和堆尾交换，下标n-1处就是最大值了；我们再把前n-1个数据调整成大堆，此时堆顶就是第二大的数据，堆顶和堆尾交换，下标n-2处就是第二大值了……直至排序完成。</strong></p>
<p>相反地，<strong>想排成降序就建小堆</strong>，道理是一样的，我们下面就以建成大堆为例。</p>
<p>堆排序的关键在于一开始建堆的方法，可以分为<strong>向下调整建堆</strong>和<strong>向上调整建堆</strong>：</p>
<div class="jb51code"><pre class="brush:cpp;">void HPCreat_Down(int* arr, int n) //向下调整算法建堆
{
//从尾结点的父结点开始往上遍历，每一个结点都进行向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, n);
}
}
void HPCreat_Up(int* arr, int n) //向上调整算法建堆
{
//从第一个结点开始往下遍历，每一个结点都进行向上调整
for (int i = 0; i < n; i++)
{
AdjustUp(arr, i);
}
}
//注：建的是大堆还是小堆，取决于AdjustUp和AdjustDown函数中的大于还是小于号，上面提到过
</pre></div>
<p>知道了建堆方式后，就能实现堆排序了：</p>
<div class="jb51code"><pre class="brush:cpp;">void HeapSort(int* arr, int n)
{
HPCreat_Down(arr, n);
//或HPCreat_Up(arr, n);
int end = n - 1;
while (end > 0)
{
Swap(&arr, &arr);
AdjustDown(arr, 0, end); //对新堆顶进行向下调整，以保证堆的性质
end--;
}
}
</pre></div>
<p>测试：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245074.png" /></p>
<p>很顺利。</p>
<p>关于两种建堆方式的时间复杂度：<br />推导需要用到数列相关定理公式，我就不再证明了，可以直接记住结果：</p>
<ul><li>向下调整建堆：T(n) = n - log<sub>2</sub>(n+1)，O(n)</li><li>向上调整建堆：T(n) = (n+1) + 2，O(n*logn)</li></ul>
<p>可见，向下调整建堆算法更好一些。</p>
<p class="maodian"></p><h2>三、堆排序的应用——TOP-K问题</h2>
<p>TOP-K问题，即求n个数据中前K个最大值或最小值，一般情况下n都很大且n >> k。</p>
<p>我们能想到的最简单的方法就是排序了，但是如果数据量太大，数据不能一下子全部加载到内存中，排序就不可取了。最佳的方式就是用堆来解决，思路为：</p>
<ul><li><strong>取前k个数据建堆，遍历剩下的n-k个数据跟堆顶比较。</strong></li><li><strong>如果找的是前k个最大值，就建小堆。若第k+1个数比堆顶大，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最大值了。</strong></li><li><strong>如果找的是前k个最小值，就建大堆。若第k+1个数比堆顶小，就用它替换堆顶，再调整堆，再比较第k+2个数和堆顶……遍历完，最后堆中的k个数就是n个数里面前的k个最小值了。</strong></li></ul>
<p>应该很好理解吧。</p>
<p>举个栗子，我先来造十万个数据，保存到一个文本文件data.txt中</p>
<div class="jb51code"><pre class="brush:cpp;">void CreatData()
{
srand(time(0));
FILE* file = fopen("data.txt", "w");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
for (int i = 0; i < 100000; i++)
{
int x = (rand() + i) % 100000 + 1;
fprintf(file, "%d\n", x);
}
fclose(file);
}
</pre></div>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245033.png" /></p>
<p>最后来实现TOP_K算法（以找前k个最小值为例）：</p>
<div class="jb51code"><pre class="brush:cpp;">void Top_K()
{
int k;
printf("请输入K:");
scanf("%d", &k);
FILE* file = fopen("data.txt", "r");
if (file == NULL)
{
perror("fopen fail!");
exit(2);
}
int* maxHeap = (int*)malloc(sizeof(int) * k);
if (maxHeap == NULL)
{
perror("malloc fail!");
exit(1);
}
for (int i = 0; i < k; i++)
{
//先将前k个数存到maxHeap中
fscanf(file, "%d", &maxHeap);
}
HPCreat_Down(maxHeap, k); //找前k个最小值，建大堆
//遍历剩下的数
int x;
while (fscanf(file, "%d", &x) != EOF) //fscanf文件读取结束会返回EOF
{
//谁小谁当堆顶
if (x < maxHeap)
{
maxHeap = x;
AdjustDown(maxHeap, 0, k);
}
}
fclose(file);
//处理完成，打印结果
for (int i = 0; i < k; i++)
{
printf("%d ", maxHeap);
}
}
</pre></div>
<p>测试：</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202601/2026010608245032.png" /></p>
<p>可以看到，每次输入一个k，都能找到前k个最小值，只不过不是按大小顺序输出的。顺带一提，这个算法的时间复杂度O(n) = k + (n - k)log<sub>2</sub>k</p>
<p class="maodian"></p><h2>总结</h2>
<p>到此这篇关于C语言顺序结构的二叉树之堆排序的文章就介绍到这了,更多相关C语言顺序结构堆排序内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区！</p>
<div class="art_xg">
<b>您可能感兴趣的文章:</b><ul><li>C语言数据结构之堆排序源代码</li><li>C语言实现堆排序的简单实例</li><li>C语言 数据结构堆排序顺序存储（升序）</li><li>C语言堆实现建堆算法和堆排序</li><li>C语言八大排序之堆排序</li><li>C语言数据结构之堆排序详解</li><li>C语言排序之 堆排序</li></ul>
</div>
</div>
<!--endmain-->
頁:
[1]