当前位置： 首页 > news >正文

搜索引擎在线保定seo建站

news 2026/4/7 4:00:44
搜索引擎在线,保定seo建站,wordpress 好不好,网站建设套餐报价目录 前言 一.堆 1.堆的概念 2.堆的存储方式 二.堆的操作方法 1.堆的结构体表示 2.数字交换接口函数 3.向上调整（难点） 4.向下调整（难点） 5.创建堆 6.堆的插入 7.判断空 8.堆的删除 9.获取堆的根(顶)元素 10.堆的遍历…

 目录

前言

一.堆

1.堆的概念

2.堆的存储方式

二.堆的操作方法

1.堆的结构体表示

2.数字交换接口函数

3.向上调整（难点）

4.向下调整（难点）

5.创建堆

 6.堆的插入

 7.判断空

8.堆的删除

 9.获取堆的根(顶)元素

10.堆的遍历

 11.销毁堆

完整代码

三.堆的应用（堆排序）

1.算法介绍

2.基本思想

3.代码实现

4.算法分析

前言

         今天我们开始学习一种二叉树，没错，那就是完全二叉树，完全二叉树又叫做堆，在此之前我们简单介绍过了完全二叉树的概念（链接：数据结构-----树和二叉树的定义与性质_灰勒塔德的博客-CSDN博客），这种类型的二叉树又有什么特点呢？代码怎么去实现呢？应用有那些呢？下面就一起来看看吧！

一.堆

1.堆的概念

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象，物理层面上是一个数组，逻辑上是一个完全二叉树。堆总是满足下列性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值；

  • 堆总是一棵完全二叉树。

  • 满足任意父节点都大于子节点的称作为大堆

  • 满足任意子节点都大于父节点的称作为小堆

  • tip:（下文会以大堆的创建为示例）

如图所示：

 

2.堆的存储方式

堆的储存原则是从上到下，从左到右，也就是说先有上面的父节点才会有子节点，先有左子节点，才会有右子节点 ，所以堆可以去通过一个数组完整的表示出来，如下图所示：

二.堆的操作方法

以下是一个堆要实现的基本功能，下面我会一一去详细解释说明

void swap(DataType* a, DataType* b);//交换数据void Adjust_Up(DataType* data, int child, int n);//向上调整void Adjust_Down(DataType* data, int parent, int n);//向下调整void Heap_Create(Heap* hp, DataType* data, int n);//创建堆bool isEmpty(Heap* hp);//判断空void Heap_Insert(Heap* hp, DataType x);//堆的插入void Heap_Del(Heap* hp);//堆的删除操作DataType Heap_Root(Heap* hp);//获取根元素void Heap_show(Heap* hp);//堆的遍历void Heap_Destory(Heap* hp);//堆的销毁

1.堆的结构体表示

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define Maxsize 50//顺序结构
//堆（完全二叉树）
typedef int DataType;	//定义数据的类型
typedef struct Heap
{int size;	//当前节点数量int capacity;	//最大容量DataType* data;	//数据储存地址
}Heap;

2.数字交换接口函数

//数据交换接口
void swap(DataType* a, DataType* b) {DataType temp = *a;*a = *b;*b = temp;
}

3.向上调整（难点）

        创建大堆时，向上调整的目的是，在有子节点位置的情况下，进行与父节点的大小比较，如果子节点大于父节点，那么就进行交换，然后新的子节点就是上一个的父节点，依次这样比较下去，最后到根节点为止，如图所示：

 代码实现：

//向上调整
void Adjust_Up(DataType* data, int child, int n) {int parent = (child - 1) / 2;while (child > 0) {//如果子节点大于父节点就进行数值交换，然后此时的子节点就是前一个父节点，再找到//新的父节点，继续进行同样的操作，直到根节点为止if (data[child] > data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

4.向下调整（难点）

        同样的还有向下调整，如果有了当前的父节点位置，那么就要跟子节点进行比较，但是子节点有左和右子节点，所以左右子节点也要去比较，取到其中比较大的子节点与父节点比较，如果这个字节点大于父节点的话，那就进行数字交换，然后新的父节点就是上一个的子节点，依次往下遍历进行同样的操作。

代码实现： 

//向下调整
void Adjust_Down(DataType* data, int parent, int n) {int child = parent * 2 + 1;while (child <n ) {if (child+1 < n && data[child] < data[child+1]){//如果右子节点大于左子节点，那就child+1，选中到右子节点child++;}if (data[child] > data[parent]) {//同样的，有了当前父节点，然后找到子节点，进行向下遍历调整操作swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

5.创建堆

已有一个数组{ 5,1,2,3,6,4,8 }，怎么把这个数组放入堆里面呢？同样的，空间申请去申请到一块连续的空间，然后依次把数据存入到这个数组里面去，最后进行向下调整，以达到堆的形式。

放入堆之后如下图所示： 

代码实现：

//创建堆
void Heap_Create(Heap* hp, DataType* data, int n) {assert(hp);hp->data = (DataType*)malloc(sizeof(DataType) * n);if (!hp->data) {printf("ERROR\n");exit(-1);}for (int i = 0; i < n; i++) {hp->data[i] = data[i];//赋值}hp->size = n;hp->capacity = Maxsize;for (int j = (n - 1) / 2; j >= 0; j--) {//创建完成了之后，就要进行向下调整Adjust_Down(hp->data, j ,hp->size);}
}

 6.堆的插入

堆的插入，就是在堆的最后面去添加一个元素，添加完成之后，就要去进行向上调整操作，如下图所示：

代码实现： 

//堆的插入
void Heap_Insert(Heap* hp, DataType x) {assert(hp);//如果此时的堆空间满了，那么就要去扩容空间if (hp->size == hp->capacity) {DataType* temp = (DataType*)realloc(hp->data,sizeof(DataType)  * (hp->capacity+1));//追加1个空间if (!temp) {printf("ERROR\n");exit(-1);}hp->data = temp;hp->data[hp->size] = x;hp->size++;hp->capacity++;}else{hp->data[hp->size] = x;hp->size++;}Adjust_Up(hp->data, hp->size - 1, hp->size);//插入后进行向上调整
}

 7.判断空

//判断空
bool isEmpty(Heap* hp) {assert(hp);return hp->size == 0;
}

8.堆的删除

堆的删除操作是删除掉根节点，过程是，先把最后一个节点与根节点进行交换，然后重新进行向下调整。（堆的删除操作，删除掉的是根节点！）

代码实现： 

//堆的删除,删除根节点
void Heap_Del(Heap* hp) {assert(hp);if (!isEmpty(hp)) {swap(&hp->data[hp->size - 1], &hp->data[0]);//根节点和尾节点进行交换hp->size--;Adjust_Down(hp->data, 0, hp->size);//向下调整}
}

 9.获取堆的根(顶)元素

//获取堆顶元素
DataType Heap_Root(Heap* hp) {assert(hp);if (!isEmpty(hp))return hp->data[0];elseexit(0);
}

10.堆的遍历

堆的遍历就直接按照数组的顺序去遍历就行了，完全二叉树的逻辑上是从上到下，从左到右去遍历的，代码如下：

//输出堆元素（按照顺序）
void Heap_show(Heap* hp) {assert(hp);if (isEmpty(hp)) {printf("The Heap is etmpy\n");return;}for (int i = 0; i < hp->size; i++)printf("%d ", hp->data[i]);
}

 11.销毁堆

//堆的销毁
void Heap_Destory(Heap* hp) {assert(hp);hp->size = hp->capacity = 0;free(hp);//释放空间
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define Maxsize 50//顺序结构
//堆（完全二叉树）
typedef int DataType;	//定义数据的类型
typedef struct Heap
{int size;	//当前节点数量int capacity;	//最大容量DataType* data;	//数据储存地址
}Heap;//数据交换接口
void swap(DataType* a, DataType* b) {DataType temp = *a;*a = *b;*b = temp;
}//向上调整
void Adjust_Up(DataType* data, int child, int n) {int parent = (child - 1) / 2;while (child > 0) {//如果子节点大于父节点就进行数值交换，然后此时的子节点就是前一个父节点，再找到//新的父节点，继续进行同样的操作，直到根节点为止if (data[child] > data[parent]){swap(&data[child], &data[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//向下调整
void Adjust_Down(DataType* data, int parent, int n) {int child = parent * 2 + 1;while (child <n ) {if (child+1 < n && data[child] < data[child+1]){//如果右子节点大于左子节点，那就child+1，选中到右子节点child++;}if (data[child] > data[parent]) {//同样的，有了当前父节点，然后找到子节点，进行向下遍历调整操作swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//创建堆
void Heap_Create(Heap* hp, DataType* data, int n) {assert(hp);hp->data = (DataType*)malloc(sizeof(DataType) * n);if (!hp->data) {printf("ERROR\n");exit(-1);}for (int i = 0; i < n; i++) {hp->data[i] = data[i];//赋值}hp->size = n;hp->capacity = Maxsize;for (int j = (n - 1) / 2; j >= 0; j--) {//创建完成了之后，就要进行向下调整Adjust_Down(hp->data, j ,hp->size);}
}//判断空
bool isEmpty(Heap* hp) {assert(hp);return hp->size == 0;
}//堆的插入
void Heap_Insert(Heap* hp, DataType x) {assert(hp);//如果此时的堆空间满了，那么就要去扩容空间if (hp->size == hp->capacity) {DataType* temp = (DataType*)realloc(hp->data,sizeof(DataType)  * (hp->capacity+1));//追加1个空间if (!temp) {printf("ERROR\n");exit(-1);}hp->data = temp;hp->data[hp->size] = x;hp->size++;hp->capacity++;}else{hp->data[hp->size] = x;hp->size++;}Adjust_Up(hp->data, hp->size - 1, hp->size);//插入后进行向上调整
}//堆的删除,取出根节点
void Heap_Del(Heap* hp) {assert(hp);if (!isEmpty(hp)) {swap(&hp->data[hp->size - 1], &hp->data[0]);//根节点和尾节点进行交换hp->size--;Adjust_Down(hp->data, 0, hp->size);//向下调整}
}//获取堆顶元素
DataType Heap_Root(Heap* hp) {assert(hp);if (!isEmpty(hp))return hp->data[0];elseexit(0);
}//输出堆元素（按照顺序）
void Heap_show(Heap* hp) {assert(hp);if (isEmpty(hp)) {printf("The Heap is etmpy\n");return;}for (int i = 0; i < hp->size; i++)printf("%d ", hp->data[i]);
}//堆的销毁
void Heap_Destory(Heap* hp) {assert(hp);hp->size = hp->capacity = 0;free(hp);//释放空间
}

三.堆的应用（堆排序）

1.算法介绍

        堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2.基本思想

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

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

3.代码实现

#include<stdio.h>
#include<assert.h>
//数据交换接口
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}//向下调整
void Adjust_Down(int* data, int parent, int n) {int child = parent * 2 + 1;while (child < n) {if (child + 1 < n && data[child] < data[child + 1]){//如果右子节点大于左子节点，那就child+1，选中到右子节点child++;}if (data[child] > data[parent]) {//同样的，有了当前父节点，然后找到子节点，进行向下遍历调整操作swap(&data[child], &data[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序算法
void Heap_sort(int* arr, int n) {assert(arr);for (int i = (n - 2) / 2; i >= 0; i--) {Adjust_Down(arr, i, n);}//先形成最大堆int end = n - 1;//从小到大排序while (end > 0) {swap(&arr[0], &arr[end]);Adjust_Down(arr, 0, end);end--;	//此时最后一个也就是当前的最大值已经排序好了}
}int main() {int a[9] = { 5,1,2,3,6,4,8,2,10 };Heap_sort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++) {printf("%d ", a[i]);}
}
//输出
//1 2 2 3 4 5 6 8 10

4.算法分析

  • 平均时间复杂度：O(nlogn)
  • 最佳时间复杂度：O(nlogn)
  • 最差时间复杂度：O(nlogn)
  • 稳定性：不稳定

 以上就是本期的内容，我们下次见！

 分享一张壁纸：

http://www.hkea.cn/news/21192/

相关文章：

  • 什么网站做调查能赚钱关键词优化报价推荐
  • 网站开发职业认知小结开发一个app平台大概需要多少钱?
  • 装修公司全包项目seo搜索引擎实训心得体会
  • 爱站网是干什么的长沙关键词排名首页
  • wordpress 教垜四川seo推广公司
  • 东莞市阳光网青岛seo服务
  • 网站弹窗在中间位置企业培训师
  • 整站下载器 安卓版域名解析查询站长工具
  • 跨境自建站模板seo推广是做什么
  • 网站建设与网页设计报告网络营销师报名入口
  • 生成前端页面的网站东莞网络营销全网推广
  • 网站及单位网站建设情况免费男女打扑克的软件
  • 公司有网站有什么好处网上开店如何推广自己的网店
  • 海口网站建设策划关键词排名优化工具有用吗
  • 请问哪里可以做网站汕头seo
  • 访问国外网站速度慢苏州关键词seo排名
  • 做网站备案照片的要求谷歌seo教程
  • wordpress站点全屏新站如何让百度快速收录
  • wordpress 会议 主题推广排名seo
  • 源码开发网站建设sem与seo的区别
  • 如何查网站的空间防恶意点击软件
  • 单位网站建设收费标准互联网推广引流
  • 网站有中文源码加英文怎么做关键词歌词完整版
  • 建设网站企业银行做网站的平台
  • 如何进行网站建设分析网站推广app软件
  • 做ppt的软件模板下载网站网站服务公司
  • 网站icp备案认证怎么做谷歌网页版入口在线
  • 高安网站建设艺考培训
  • 主流的网站开发技术百度推广后台管理
  • 传奇网站模板免费下载优化网络搜索引擎