前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >关于堆

关于堆

作者头像
Noneplus
发布2020-01-22 09:49:42
5480
发布2020-01-22 09:49:42
举报
文章被收录于专栏:开发笔记

关于堆

堆本质上是用数组实现的二叉树。

大根堆:一棵完全二叉树,满足任一节点都比其子节点大;用于升序排列

小根堆:一棵完全二叉树,满足任一节点都比其他子节点小;用于降序排列

1570680278068
1570680278068

如何用数组实现堆?

节点在数组中的位置index 和它的父节点以及子节点的索引之间有一个映射关系。

代码语言:javascript
复制
parent(i) = floor((i - 1)/2)             //floor函数表示向下取整
left(i)   = 2i + 1
right(i)  = 2i + 2
代码语言:javascript
复制
[ 10, 7, 2, 5, 1 ]

Node

Array index (i)

Parent index

Left child

Right child

10

0

-1

1

2

7

1

0

3

4

2

2

0

5

6

5

3

1

7

8

1

4

1

9

10

使用数组索引代替指针,节约了空间,但是需要进行更多的计算。(这就是交易)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-11-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 关于堆
  • 如何用数组实现堆?
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档