Ted 带你学习数据结构 之 二叉堆（Binary Heap）

本文主要是介绍Ted 带你学习数据结构 之 二叉堆（Binary Heap），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉堆（Binary Heap）

---

（1）structure property

Heap（堆）是一个除了底层节点外的完全填满的二叉树，底层可以不完全，左到右填充节点。（a heap is a binary tree that completely filled, with the exception of bottom level, which is filled from left to right.）这样的树叫做完全二叉树。

完全二叉堆的通俗解释为： 上层节点全满时，下层才能有节点；且下层节点必须是从左往右添加的。

一个高度为h 的完全二叉树应该有以下的性质：

a) 有2^h到2^h-1个节点

b) 完全二叉树的高度为[logN](向下取整)

此时注意，当N为2的多次方时，h=logN+1;

c)他的左子节点在2*i，右子节点在（2*i+1）

d) 它的父节点在【i/2】(向下取整)

二叉堆是一种逻辑上的数据结构，而它是由数组来实现的。

下图显示了完全二叉树与数组的对应关系：

这篇关于Ted 带你学习数据结构 之 二叉堆（Binary Heap）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---