数据结构:堆和堆排序

这篇具有很好参考价值的文章主要介绍了数据结构:堆和堆排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构:堆和堆排序

1.二叉树的存储结构

1.顺序结构

顺序结构存储就是使用数组来表示一棵二叉树一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2.链式结构

二叉树的链式存储是使用链表来表示一棵二叉树,即用指针链接来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。
数据结构:堆和堆排序,数据结构初阶,数据结构,堆

2.堆

堆实际上就是一棵完全二叉树

其性质为:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

大堆和小堆:

  • 每个节点的值都大于或等于其子节点的值,为大堆;反之为小堆。

3.堆的实现

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
// (大小)堆的实现(堆的结构与特点发现与数组下标有紧密关系)因此可以使用顺序表结构体
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

// 堆的构建
void HeapCreate(Heap* hp);

// 堆的销毁
void HeapDestory(Heap* hp);
// 向上调整
void AdjustUp(HPDataType* a, size_t childposition);

// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 向下调整
void AdjustDown(HPDataType* a, int size, size_t parentposition);

// 堆的删除
void HeapPop(Heap* hp);

// 取堆顶的数据
HPDataType HeapTop(Heap* hp);

// 堆的数据个数
int HeapSize(Heap* hp);

// 堆的判空
bool HeapEmpty(Heap* hp);

#include "Heap.h"

// 堆的构建
void HeapCreate(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	free(hp->a);
	hp->capacity = 0;
	hp->size = 0;
	hp = NULL;
}
// 向上调整
void AdjustUp(HPDataType* a, size_t childposition)
{
	assert(a);

	size_t parentposition = (childposition - 1) / 2;
	while (childposition > 0)
	{
		// 小堆
		if (a[childposition] < a[parentposition])
		{
			// 交换孩子和父亲的值
			HPDataType  tmp = a[childposition];
			a[childposition] = a[parentposition];
			a[parentposition] = tmp;

			childposition = parentposition;
			parentposition = (parentposition - 1) / 2;
		}
		else
		{
			return;
		}
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	// 检查容量
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;

		HPDataType* newa = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (newa == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = newa;
		hp->capacity = newcapacity;
	}


	hp->a[hp->size] = x;
	hp->size++;

	// 向上调整(可用递归可用循环,此处我们用循环实现)
	AdjustUp(hp->a, hp->size - 1);


}
// 向下调整
void AdjustDown(HPDataType* a, int size, size_t parentposition)
{
	assert(a);

	size_t childposition = a[1] < a[2] ? 1 : 2;
	while (childposition < size)
	{
		if (a[childposition] < a[parentposition])// 小堆
		{
			HPDataType tmp = a[childposition];
			a[childposition] = a[parentposition];
			a[parentposition] = tmp;

			parentposition = childposition;
			childposition = a[childposition * 2 + 1] < a[childposition * 2 + 2] ? childposition * 2 + 1 : childposition * 2 + 2;
		}
		else
		{
			break;
		}
	}
}

// 堆的删除(删除堆顶元素)
void HeapPop(Heap* hp)
{
	assert(hp);
	if (hp->size == 0)
	{
		printf("堆为空,无法删除\n");
		return;
	}
	HPDataType tmp = hp->a[0];
	hp->a[0] = hp->a[hp->size - 1];
	hp->size--;

	AdjustDown(hp->a, hp->size, 0);

}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	if (hp->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

4.堆排序(选择排序中的一类)

看到堆排序我们会想到是不是利用我们自己造轮子写出来的堆这个数据结构和接口函数来实现排序呢?

假设我们要对一个数组里的元素进行排序,我们可能想到这样做:

  1. 将数组里的元素通通插入到堆中,插入进去的元素自然就形成了一种排序结构。
  2. 再将堆里的数据取出来放回到原数组中从而进行排序。

弊端:这样进行‘’堆排序‘’实际上是十分复杂和浪费空间和时间的,这个方法前提下我们必须要先自己实现一个堆,再然后堆的构建也是要开辟内存空间的十分低效。

一次建堆的时间的复杂度是(向上调整建堆和向下调整建堆):
O ( N ∗ log ⁡ N ) O(N*\log_{}{N}) O(NlogN)


实际的堆排序:

记忆:升序建大堆,降序建小堆。

1. 基本思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

① 将待排序的序列构造成一个==最大堆==,此时序列的最大值为根节点。
② 依次将根节点与待排序序列的最后一个元素交换。
③ 再维护从根节点到该元素的前一个节点为最大堆,**如此往复,最终得到一个递增序列**。

2.代码实现

// 向上调整
void AdjustUp(int* a, size_t childposition)
{
	assert(a);
	size_t parentposition = (childposition - 1) / 2;
	while (childposition > 0)
	{
		// 大堆
		if (a[childposition] > a[parentposition])
		{
			// 交换孩子和父亲的值
			int  tmp = a[childposition];
			a[childposition] = a[parentposition];
			a[parentposition] = tmp;

			childposition = parentposition;
			parentposition = (parentposition - 1) / 2;
		}
		else
		{
			return;
		}
	}
}

void swap(int* start, int* end)
{
	int tmp = 0;
	tmp = *start;
	*start = *end;
	*end = tmp;
}

// 堆排序
void HeapSort(int* a, int n)
{
	int i = 0;
	// 当数据个数大于1时才进行排序,否则直接就是有序的
	while (n > 1)
	{
		// 建大堆使得最大的数位于堆顶部
		for (i = 1; i < n; i++)
		{
			AdjustUp(a, i);
		}
		// 堆顶元素与堆最后一个元素交换位置
		swap(&a[0], &a[n - 1]);
		// 除去堆最后一个位置的元素重新建立大堆,如此往复,最终得到一个递增序列
		n--;
	}
}

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

void HeapSort(int* a, int n);
void AdjustUp(int* a, size_t childposition);

int main()
{
	int a[] = { 4,6,2,1,5,8,9,3,7,10 };
	HeapSort(a, sizeof(a) / sizeof(a[0]));

	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

数据结构:堆和堆排序,数据结构初阶,数据结构,堆

数据结构:堆和堆排序,数据结构初阶,数据结构,堆文章来源地址https://www.toymoban.com/news/detail-796247.html

到了这里,关于数据结构:堆和堆排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构初阶】八大排序(三)——归并排序&&计数排序

    大家好我是沐曦希💕 往期博客:【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 【数据结构初阶】八大排序(二)——快速排序冒泡排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一

    2024年02月03日
    浏览(133)
  • 【数据结构初阶】八大排序(二)——快速排序&&冒泡排序

    大家好我是沐曦希💕 书接【数据结构初阶】八大排序(一)——希尔排序堆排序直接插入排序直接选择排序 基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是: 将键值较大的记录向序列的尾部移动,键值较小

    2024年02月21日
    浏览(117)
  • 数据结构初阶之排序

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 一.前言 二.选择排序 2.1选择排序思想 2.2代码实现 三.快速

    2024年01月18日
    浏览(44)
  • 『初阶数据结构 • C语言』⑥ - 插入排序&希尔排序

    学习目标 写在前面 1.插入排序 2.插入排序实战  3.插入排序的实现  4.插入排序的效率 5.平均情况 6.希尔排序 7.希尔排序的实现 8.希尔排序的效率 9.总结   之前我们衡量一个算法的效率时,都是着眼于它在最坏情况下需要多少步。原因很简单,连最坏的情况都做足准备了,其

    2024年02月15日
    浏览(43)
  • 数据结构初阶之插入排序与希尔排序详解

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 一.前言 二.插入排序 2.1插入排序的思想 2.2代码实现 三.希

    2024年02月02日
    浏览(48)
  • 【初阶数据结构】——堆排序和TopK问题

     ========================================================================= 个人主页 代码仓库 C语言专栏 初阶数据结构专栏 Linux专栏  ========================================================================= 接上篇二叉树和堆的引入 =========================================================================  目录 前言 建堆 插

    2024年02月07日
    浏览(44)
  • 『初阶数据结构 • C语言』④ - 冒泡排序

      本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。      本章内容 写在前面 1.冒泡排序 2.冒泡排序实战 3.冒泡排序的实现 4.冒泡排序的效率 5.二次问题 6.线性解决 7.总结     大 O记法能客观地衡量

    2024年02月16日
    浏览(46)
  • 『初阶数据结构 • C语言』⑤ - 选择排序

    本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余,我决定把这本书精彩的部分摘录出来与大家分享。     目录 写在前面 1.选择排序 2.选择排序实战 3.选择排序的实现 4.选择排序的效率 5.忽略常数 6.大O的作用 7.总结     大 O 是一种能够比较算法效

    2024年02月14日
    浏览(45)
  • 【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想: 假设现在已经有一个有序序列,如果有一个数字插入到这段序列的末尾,我们会选择拿这个数和它前面的每个数字都比较一遍,如果前面的数字比他大,那我们就让前面的数字赋值到这个被插入的数字位置,依次与前面的数

    2024年02月01日
    浏览(117)
  • 『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

     = 目录 0.写在前面 1.什么是堆? 2. 堆排序 2.1 建堆 2.1.1 AdjustUp(向上调整算法) 2.1.2 AdjustDown(向下调整算法) 2.2 两种建堆算法的时间复杂度 2.2.1 AdjustUp建堆的时间复杂度 2.2.2 AdjustDown建堆的时间复杂度 2.3 排序 3.堆排序的时间复杂度 完整源码 你是否对堆排序早有耳闻?身

    2024年02月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包