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

网站建设方案费用预算西安核心关键词排名

news 2026/4/6 23:50:45
网站建设方案费用预算,西安核心关键词排名,网站semseo先做哪个,网站建设与维护考试答案目录 一、堆的概念及结构 二、堆的实现 1.堆的定义 2堆的初始化 3堆的插入 ​编辑 4.堆的删除 5堆的其他操作 6代码合集 三、堆的应用 （一）堆排序（重点） （二）TOP-K问题 一、堆的概念及结构 堆的…

目录

一、堆的概念及结构

二、堆的实现

1.堆的定义

2堆的初始化

3堆的插入

​编辑 4.堆的删除

5堆的其他操作

6代码合集

三、堆的应用

（一）堆排序（重点）

（二）TOP-K问题

一、堆的概念及结构

堆的性质：

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

  • 堆总是一棵完全二叉树（但实现起来是线性表）。

二、堆的实现

1.堆的定义

//大堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;

2堆的初始化

//堆的初始化
void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}

3堆的插入

//从孩子的位置向上调整函数
void AdjustUp(HPDataType* a, int child)//child是向上调整数的下标
{int parent = (child - 1) / 2;while (child>0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) *  php->capacity*2);if (php->a == NULL){perror("malloc fail");return;}// 将旧数据拷贝到新内存中for (int i = 0; i < php->size; i++){tmp[i] = php->a[i];}free(php->a);php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//刚才size++了，所以向上调整的孩子的位置是size-1
}

 4.堆的删除

删除堆顶，用处：可用来排序选出前几名

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

难点：

  • 向下比怎么比？下面哪个儿子大就和谁比

  • 怎么判断已经到叶子节点了？计算该节点的孩子节点有没有超出范围

//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{int child = parent * 2 + 1;//先默认左孩子大while (child < n){//选出左右孩子中大的那一个  右孩子和左孩子的关系：大一if (child+1<n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆的删除
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个数php->size--;AdjustDown(php->a, php->size,0);
}

如果想要取前k个，那么修改如下： 

5堆的其他操作

//显示堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
//显示堆的大小
int HeapSize(HP* php)
{assert(php);return php->size;
}
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

6代码合集

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
//大堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//堆的插入
void HeapPush(HP* php, HPDataType x);
//堆的删除
void HeapPop(HP* php);
//显示堆顶元素
HPDataType HeapTop(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//显示堆的大小
int HeapSize(HP* php);
//销毁
void HeapDestroy(HP* php);
//从孩子的位置向上调整函数
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);

Heap.c

#include"Heap.h"
//堆的初始化
void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp = *p1;*p1 =*p2;*p2 = temp;
}
//从孩子的位置向上调整函数
void AdjustUp(HPDataType* a, int child)//child是向上调整数的下标
{int parent = (child - 1) / 2;while (child>0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) *  php->capacity*2);if (php->a == NULL){perror("malloc fail");return;}// 将旧数据拷贝到新内存中for (int i = 0; i < php->size; i++){tmp[i] = php->a[i];}free(php->a);php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//刚才size++了，所以向上调整的孩子的位置是size-1
}
//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{int child = parent * 2 + 1;//先默认左孩子大while (child < n){//选出左右孩子中大的那一个  右孩子和左孩子的关系：大一if (child+1<n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆的删除
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个数php->size--;AdjustDown(php->a, php->size,0);
}
//显示堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size==0;
}
//显示堆的大小
int HeapSize(HP* php)
{assert(php);return php->size;
}
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

test.c

#include"Heap.h"
int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 4);HeapPush(&hp, 18);HeapPush(&hp, 42);HeapPush(&hp, 12);HeapPush(&hp, 2);HeapPush(&hp, 3);int k = 0;scanf_s("%d", &k);while (!HeapEmpty(&hp)&&k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);//和栈非常相似，想把老二取出来就得把老大干掉}printf("\n");return 0;
}

三、堆的应用

（一）堆排序（重点）

①. 建堆
  • 升序：建大堆
  • 降序：建小堆
建堆方式：
向上调整建堆：模拟的是插入数据的过程 
//排升序建大堆
void HeapSort(int* a, int n)
{//建大堆for (int i = 1; i < n; i++){AdjustUp(a, i);}
}

向下调整建堆（左右子树必须是大堆或小堆（插入之前得是堆））：

void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0;--i)//先找到最后一个非叶子结点即上图的6 n-1是最后一个数据的下标，再-1除以2就是父节点{AdjustDown(a, n, i);}
}

注：向下建堆的效率O（N）比向上建堆的效率O（N*logN）高

数学证明如下：

②. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

代码实现：

#include<stdlib.h>void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp = *p1;*p1 =*p2;*p2 = temp;
}
//从孩子的位置向上调整函数
void AdjustUp(HPDataType* a, int child)//child是向上调整数的下标
{int parent = (child - 1) / 2;while (child>0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{int child = parent * 2 + 1;//先默认左孩子大while (child < n){//选出左右孩子中大的那一个  右孩子和左孩子的关系：大一if (child+1<n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//O(n*logn)
//排升序建大堆
void HeapSort(int* a, int n)
{//向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0;--i)//n-1是最后一个数据的下标，再-1除以2就是父节点
{AdjustDown(a, n, i);
}int end = n - 1;while (end>0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
int main()
{int a[10] = { 2,1,5,7,6,8,0,9,3 };HeapSort(a, 9);return 0;
}

③堆排序的时间复杂度

所以如果用来排序的话，无论是向上调整还是向下调整建堆，总的时间复杂度都是O(N*logN)

（二）TOP-K问题

TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。
比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能
数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前 K 个元素来建堆
前 k 个最大的元素，则建小堆
前 k 个最小的元素，则建大堆(和堆排序有点反过来的意思)
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素 
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void PrintTopK(const char* file, int k)
{// 1. 建堆--用a中前k个元素建小堆int* topk = (int*)malloc(sizeof(int) * k);assert(topk);//读文件FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//读出前K个数建堆for (int i = 0; i < k; ++i){fscanf(fout, "%d", &topk[i]);}//向下调整建堆for (int i = (k - 1 - 1) / 2; i >= 0; --i){AdjustDown(topk, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换int val = 0;int ret= fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0])//如果新元素大于堆顶元素，那么替换堆顶元素{topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}//打印这个数组for (int i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);fclose(fout);
}
void TestTopk()
{//为了测试而造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);PrintTopK(file,10);
}
int main()
{TestTopk();return 0;
}

注意：这里是建小堆，AdjustDown里面需要调一下，之前是建大堆用的AdjustDown

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

相关文章：

  • 苏中建设集团官方网站电商软文广告经典案例
  • 网站开发需要什么开发工具代做百度首页排名价格
  • 北京网站设计多少钱微信引流推广
  • 网站建设实施背景分析百度指数里的资讯指数是什么
  • 小程序定制开发深圳公司网站的优化seo
  • 构建一个网站域名查询平台
  • 蚌埠网站关键词优化推广下载
  • 看房地产的app在哪看aso安卓优化
  • 网站与域名的区别扬州整站seo
  • 哪些网站可以进行域名注册公司关键词seo
  • 如何申请一个网站 做视频百度小说搜索热度排行榜
  • 天津做网站选择津坤科技b重庆seo教程搜索引擎优化
  • 什么网站做热能表好百度一下电脑版首页网址
  • 点击图片直接进入网站怎么做如何使用免费b站推广网站
  • 手机网站建设软件怎么在百度上做广告推广
  • 南京做网站团队手机app免费制作平台
  • 17173游戏网搜索优化指的是什么
  • 公司做网站需要给百度交钱吗百度竞价推广方案
  • 网站建设的关键seo推广小分享
  • 写小说的小网站百度关键词排名优化
  • 制作网站的成本规划公司如何建立网站
  • html语言做网站石嘴山网站seo
  • 做最好的言情网站官网seo优化
  • 云南建设监理协会网站营销失败案例分析
  • 怎么样做淘宝优惠券网站搜索引擎营销的优缺点
  • wordpress动态订单seo社区
  • 网站域没到期不能续费吗google谷歌搜索
  • 厦门好的做网站公司网络营销推广方式都有哪些
  • 重庆市建设工程信息官网站自己做网站的流程
  • 网站建设公司怎么做网络营销网站推广