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

网站建设以推广新闻发稿平台

网站建设以推广,新闻发稿平台,巴城镇建设网站,上海营销型网站建设文章目录堆的实现堆向下调整算法堆的创建堆的插入堆的删除堆的代码实现堆的应用堆的实现 堆是属于操作系统进程地址空间内存区域的划分。 我们下面实现数据结构中的堆。 堆是一个完全二叉树&#xff1a;分为小根堆和大根堆。 小根堆&#xff1a;任何一个节点的值都<孩子的…

文章目录

    • 堆的实现
      • 堆向下调整算法
      • 堆的创建
      • 堆的插入
      • 堆的删除
      • 堆的代码实现
      • 堆的应用


堆的实现

堆是属于操作系统进程地址空间内存区域的划分。

我们下面实现数据结构中的堆。
堆是一个完全二叉树:分为小根堆和大根堆。
小根堆:任何一个节点的值都<=孩子的值
在这里插入图片描述

大根堆:任何一个节点的值都>=孩子的值
在这里插入图片描述

应用:

1.堆排序,第一个时间复杂度达到–O(N*log N)的排序。
2.topK问题:找一堆数据前K大或者前K小。

数组下标计算父子关系公式:

左孩子:leftchild = parent*2 + 1
右孩子:rightchild = parent*2 + 2
孩子算父亲:parent = (child - 1) / 2

堆向下调整算法

给出一个数组,逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。
前提:左右子树必须是一个堆,才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

在这里插入图片描述

堆的创建

给出一个数组,逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们把它构建成一个堆。根节点左右子树不是堆,这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
采用向下调整建堆。

int a[] = {1,5,3,8,7,6}; 

在这里插入图片描述

堆的插入

先插入一个数组的尾上,再进行向上调整算法,直到满足堆。

1.先将元素插入到对的末尾,即最后一个孩子之后。
2.插入之后如果堆的性质遭到了破坏,将新插入节点顺着双亲往上调整到合适位置即可。

在这里插入图片描述
AdjustUp

堆的删除

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

1.将堆顶元素与堆中追后一个元素进行交换。
2.删除堆中最后一个元素
3.将堆顶元素向下调整到满足堆特性为止。

在这里插入图片描述

堆的代码实现

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 HeapPrint(HP* php);void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);void HeapInit(HP* php);
void HeapDestroy(HP* php);
// xֶ̬
void HeapPush(HP* php, HPDataType x);
// ɾѶԪ
void HeapPop(HP* php);
// ضѶԪ
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

Heap.c

#include "Heap.h"void HeapPrint(HP* php)
{for (int i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 插入x继续保持堆形态 -- logN
void HeapPush(HP* php, HPDataType x)
{assert(php);// 扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity*sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a, int n, int parent)
{int minChild = parent * 2 + 1;while (minChild < n){// 找出小的那个孩子if (minChild+1 < n && a[minChild + 1] < a[minChild]){minChild++;}if (a[minChild] < a[parent]){Swap(&a[minChild], &a[parent]);parent = minChild;minChild = parent * 2 + 1;}else{break;}}
}// 删除堆顶元素 -- 找次大或者次小 -- logN
// O(logN)
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);assert(!HeapEmpty(php));return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

堆的应用

堆排序:

1.建堆:
升序:建大堆
降序:建小堆
2.利用堆删除思想来进行排序

int a[] = {201741653}; 

在这里插入图片描述

建堆和堆删除中都用到了向下调整,因此必须掌握了向下调整。

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

相关文章:

  • php网站 上传百度信息
  • 如何创做网站长春今日头条新闻
  • 网站建设与维护协议怎么去推广自己的网站
  • 个人交互式网站备案搜狗站长平台验证网站
  • 海外代购网站怎么做seo排名赚app官网
  • 怎么制造网站广告类的网站
  • 网站制作维护费 归属淘宝网店代运营正规公司
  • 西安做网站-西安网站建设-西安网站制作-西安网络公司_千秋网络北京网站优化服务
  • 加盟网站有哪些不屏蔽的国外搜索引擎
  • 怎样找公司做单的网站建设网站的十个步骤
  • 网络营销的发展概述网络seo招聘
  • 济南网站建设公司推荐软件推广方案经典范文
  • 网易做网站吗关键字有哪些
  • 企业自己做网站对网络营销的认识800字
  • 青州建设局网站百度搜索广告怎么收费
  • 网站二级目录解析搜索引擎营销的基本方法
  • 建设的网站后台会自动退出是正常的网络营销案例分析ppt
  • wp网站如何做多级联动筛选框百度风云榜电视剧排行榜
  • 像做游戏一样编程的网站网络推广外包
  • php怎么做网站快湖南seo网站多少钱
  • eclipse怎么做网站搭建网站工具
  • wordpress网站描述插件网络运营具体做什么
  • 东营做网站的公司公司网站怎么做
  • 聊城建设网站网站统计代码
  • 常用搜索网站今日国际新闻最新消息
  • 做新浪网网站所需的条件网站seo优化有哪些方面
  • 怎么快速做网站什么是百度权重
  • 给特宝网站商家网址怎样做网站关键词快速排名服务
  • 合肥外贸网站建设公司社区推广
  • 公司名称吉凶查询大吉app搜索优化