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

四川手机网站设计seo优化推广工程师招聘

四川手机网站设计,seo优化推广工程师招聘,建设银行唐山分行网站,wordpress加入下载标签目录 堆的概念及结构 ​编辑 堆的实现 实现堆的接口 堆的初始化 堆的打印 堆的销毁 获取最顶的根数据 交换 堆的插入(插入最后) 向上调整(这次用的是小堆) 堆的删除(删除根) 向下调整(这次用的…

目录

堆的概念及结构

​编辑

堆的实现 

实现堆的接口

堆的初始化

堆的打印

堆的销毁

获取最顶的根数据

 交换

堆的插入(插入最后)

向上调整(这次用的是小堆)

堆的删除(删除根)

向下调整(这次用的小堆)

堆排序

TOP-K问题


堆的概念及结构

如果有一个关键码的集合 K = { , , , ,},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0, 1 , 2…,则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

小根堆:父亲节点大于等于孩子节点

大根堆:父亲节点小于等于孩子节点 

堆的实现 

实现堆的接口

#define CRT_SECURE_NO_WARNING 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>//二叉树-堆
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void AdjustUp(HPDataType* a, int child);void AdjustDown(HPDataType* a, int n, int parent);//交换
void Swap(HPDataType* p1, HPDataType* p2);
//打印
void HeapPrint(HP* php);
//初始化
void HeapInit(HP* php);
//
void HeapInitArray(HP* php, int* a, int n);
//销毁
void HeapDestroy(HP* php);
//插入
void HeapPush(HP* php, HPDataType x);
//删除
void HeapPop(HP* php);
//返回最顶数据
HPDataType HeapTop(HP* php);
//判空
bool HeapEmpty(HP* php);

堆的初始化

//初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

堆的打印

void HeapPrint(HP* php)
{assert(php);//最后一个孩子下标为size-1for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}

堆的销毁

//销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

获取最顶的根数据

//获取根数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

 交换

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

堆的插入(插入最后)

先考虑扩容,将数据插到最后,再用向上调整法。

//插入数据
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php->size == php->capacity)//有效元素个数和容量是否相等{//相等的情况分两种:1.容量为0,先扩4个sizeof   2.容量占用满了,扩2个int newCapacity =php->capacity == 0 ? 4 : php->capacity * 2;//返回扩容后的内存新地址							//扩容后的新大小HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}//扩容后的新地址php->a = tmp;//新容量php->capacity = newCapacity;}//   php->size下标位置  先将x放最后,后面再调整php->a[php->size] = x;//   有效数据++php->size++;//   向上调整     //size-1为新插入数据的下标AdjustUp(php->a, php->size - 1);}

向上调整(这次用的是小堆)

向上调整的前提:左右子树是堆 ,时间复杂度O(logN)

//向上调整                    //新插入的数据下标
void AdjustUp(HPDataType* a, int child)
{   //定义其父节点的下标int parent = (child - 1) / 2;//循环while (child > 0){//如果子小于父就交换  (小堆)if (a[child] < a[parent]){//数值交换Swap(&a[child], &a[parent]);//下标child = parent;parent = (parent - 1) / 2;}else{break;}}
}

堆的删除(删除根)

先判空,看下是否还有元素可以删除。根数据先和最后一个孩子交换位置,孩子再向下调整。

//删除
void HeapPop(HP* php)
{assert(php);//确保有元素可删assert(php->size > 0);//最后一个孩子和要删除的根交换Swap(&php->a[0], &php->a[php->size - 1]);//有效元素size减减,相当于删除了交换后的原来的根--php->size;//删除后向下调整AdjustDown(php->a, php->size, 0);}

向下调整(这次用的小堆)

向下调整的前提:左右子树是堆 

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;//n下标位置已经没有数了while (child < n){//选小的孩子往上浮(小堆)if (child + 1 < n && a[child + 1] < a[child]){++child;}//若小的孩子都小于父,则交换if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//交换后下来的数重新变成parent,继续向下调整parent = child;child = parent * 2 + 1;}}
}

堆排序

1. 建堆
升序:建大堆
降序:建小堆
2. 利用堆删除思想来进行排序
建堆:向上调整法建堆的时间复杂度:O(N*logN)
           向下调整法建堆的时间复杂度:O(N)
可以用堆删除思想向下调整法将栈顶和最后一个元素交换,依次将最大的次大的......往后放,就达到了升序排列。
void HeapSort(int* a, int n)
{//建堆  这里可以选建大堆还是小堆// 向下调整建堆// O(N)for (int i = (n-1-1)/2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

TOP-K问题

TOP-K 问题:即求数据结合中前 K 个最大的元素或者最小的元素,一般情况下数据量都比较大
比如:专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了 ( 可能
数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前 K 个元素来建堆
k 个最大的元素,则建小堆
k 个最小的元素,则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K 个元素依次与堆顶元素比完之后,堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素

先创建一个包含有10000000个数的data.txt文本文件。

void CreateNDate()
{// 造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

前k个建小堆(堆顶元素为k中最小),剩余n-k个依次和堆顶元素比较,比k大就插入堆中(插入堆插入向下调整法),完成后打印前k个元素。

void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout = fopen(filename, "r");if (fout == NULL){perror("fopen fail");return;}//给堆开辟空间int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc fail");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 前k个数建小堆for (int i = (k - 2) / 2; i >= 0; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > minheap[0]){// 替换你进堆minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");free(minheap);fclose(fout);
}

假设k等于5,成功打印出前5个最大的数据

http://www.hrbkazy.com/news/20459.html

相关文章:

  • 做网站编辑要有逻辑吗网站seo分析报告
  • 描述对于营销型网站建设很重要飘红效果更佳临沂百度代理公司有几个
  • 教育门户网站系统建设方案百度指数工具
  • 思途旅游网站建设最新军事动态最新消息
  • 自己如何做购物网站百度热搜seo
  • 湖州公众号开发公司上海seo推广
  • html网站的直播怎么做竞价托管哪家专业
  • 注册了域名怎么做网站百度手机提高关键词排名
  • 如何做高清pdf下载网站百度用户服务中心官网
  • 深圳市专业做网站nba球队排名
  • 体检营销型网站营销推广软文案例
  • 投稿的网站网站seo外包靠谱吗
  • 网站里可以添加视频做背景吗国外网站推广平台有哪些?
  • phpcmsv9中英文网站安装百度一下
  • 一个网站要注意哪些问题大连今日新闻头条
  • 国外装修网站模板简单的seo
  • 网站制作软件 aws山西seo顾问
  • 企业建站业务还能做吗seo是什么的缩写
  • 做采购常用的几个网站哪个平台可以买卖链接
  • b2c网站建设网络营销工具包括
  • 广州 网站建设 行价瑞金网络推广
  • 信息类网站怎么做厦门网站设计公司
  • 学做烘焙的网站北京广告公司
  • 网站管理的内容网页制作软件手机版
  • 做网站赤峰千锋教育官网
  • 汕头做网站多少钱互联网营销师证书查询入口
  • 百度网页版网址宝鸡seo优化
  • 国际旅游网站设计报告seo流程
  • 中国专业做鞋子的网站中国优秀网页设计案例
  • 网页设计与制作app上海seo推广公司