堆
堆 是一种特殊的完全二叉树结构,通常,它有两种类型:最小堆 和 最大堆。
最小堆(min heap)是父节点的值恒小于等于子节点的值。
最大堆(max heap)是父节点的值恒大于等于子节点的值。
二叉堆的性质
任意节点小于(或大于)它的所有子节点,最小值(或最大值)在堆的根上。
堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
二叉堆的实现
堆的存储结构
堆一般可以用数组的方式来存储,数组的顺序其实就是堆层级遍历的结果。
堆的插入
由于堆是一个完全二叉树,每次总是先填满上一层,再在下一层从左往右依次插入。
插入步骤:
1.首先将新元素增加到堆的末尾。
2.然后在新元素与其父节点的值比较,如果新元素小于父节点的值则将两者交换位置。
3.不断进行第2步操作,直到不需要交换元素,或者达到堆顶。
最后就会得到一个最小堆,上面交换元素的过程叫做上滤。
堆的删除
堆的删除和插入操作是刚刚相反的,插入是从下往上调整堆,删除是从上往下调整堆。
删除步骤:
1.首先删除堆顶元素。
2.然后在比较左右子节点,将小的元素上调。
3.不断进行步骤2,直到不需要调整或者调整到堆底了。
上面交换元素的过程叫做下滤。
总结
堆有两种类型,最大堆和最小堆,并且堆总是一颗完全树。
由于堆的 父节点的值恒小于等于子节点的值 或者 父节点的值恒大于等于子节点的值,可以作为 Top n 使用。
堆(通常是二叉堆)常用于排序。这种算法称作堆排序。
PS:
清山绿水始于尘,博学多识贵于勤。
我有酒,你有故事吗?
微信公众号:「清尘闲聊」。
欢迎一起谈天说地,聊代码。
网友评论