代码拉取完成,页面将自动刷新
同步操作将从 turnon/blog 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
title: 堆
date: 2015-03-09 16:01:27
categories:
- 数据结构和算法
- 树
tags:
- 数据结构
- 树
- 二叉树
- 堆
permalink: /pages/99ac45/
堆(Heap)是一个可以被看成近似完全二叉树的数组。
堆可以分为大顶堆和小顶堆。
对于每个节点的值都大于等于子树中每个节点值的堆,叫作“大顶堆”。
对于每个节点的值都小于等于子树中每个节点值的堆,叫作“小顶堆”。
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
堆常见的操作:
堆结构的一个常见应用是建立优先队列(Priority Queue)。
求 Top K 的问题抽象成两类。一类是针对静态数据集合;另一类是针对动态数据集合
在优先级队列中,数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的,最先出队。
堆和优先级队列非常相似:往优先级队列中插入一个元素,就相当于往堆中插入一个元素;从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素。
参考:Java 的
PriorityQueue
类
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。