使用数组构建的树形结构(完全二叉树)
没有父子指针的逻辑
最大值、最小值
堆排序
优先队列
堆一般分两种:大顶堆、小顶堆,两者区别在于节点的排序方式不一样。

大顶堆/小顶堆

在大顶堆中,父节点的值比每一个子节点的值都要大
在小顶堆中,父节点的值比每一个子节点的值都要小

如:
heap
堆数组为:【11,9,6,4,5,3,2】
在堆中,每个父节点都比子节点大,则满足定义说每个子节点都大,也就是所谓的”堆属性”。
11比[9 6]大,9比[4 5]大,6比[3 2]大,小顶堆则反之。

  • 根据属性可知,大顶堆中根节点存放的是最大的节点,小顶堆中根节点存放的是最小的节点
  • 若为大顶堆,则根节点为最大,也就是说数组中第一个数据最大的,但是不能确定哪个叶子节点是最小,叶子节点的排序是未知的,小顶堆亦如此。

调整(堆排序)

一棵无序的树,经过多次的调整[调整为符合大顶堆/小顶堆的属性],最终会变成有序
每一次的调整都得符合原则
原则:从上到下,从左到右,交换根节点和末尾节点
末尾节点:数组的最后一个数值(已经调整过的节点不包括在内)

如上面例子:

  • 第一次调整:根节点【11】和末尾节点【2】交换,并把到【11】连线变成虚线(标识已经调整过了),[11]已经是最大了,后续的排序不需要再需要这个节点了

heap

  • 第二次调整:除【11】以外的节点进行堆属性调整,按照大顶堆的规则调整

heap

  • 第三次调整:根节点【9】和末尾节点【3】交换,并把连线变成虚线

heap

  • 第四次调整:除【11】【9】以外的节点进行堆属性调整,按照大顶堆的规则调整

heap

  • 第五次调整:根节点【6】和末尾节点【2】交换,并把连线变成虚线

heap

  • 第六次调整:除【11】【9】【6】以外的节点进行堆属性调整,按照大顶堆的规则调整

heap

  • 第七次调整:根节点【5】和末尾节点【2】交换,并把连线变成虚线

heap

  • 第八次调整:除【11】【9】【6】【5】以外的节点进行堆属性调整,按照大顶堆的规则调整

heap

  • 第九次调整:根节点【4】和末尾节点【3】交换,并把连线变成虚线

heap

  • 第十次调整:除【11】【9】【6】【5】【4】以外的节点进行堆属性调整,【3】【2】满足堆属性,不需要调整,只需要交换即可

heap

输出

经过多次的调整,最后形成的树为有序(降序),根据规则,从上到下,从左到右,数组为【11,9,6,5,4,3,2】,降序的操作跟大顶堆的类似,用的是小顶堆操作即可。
调整的数据只发生在剩余没没有被调整的数据,已调整的数据不应该再次放入到调整数组中
每一次的调整都像是一种选择排序

添加

添加一个元素,在数组的尾部,如以上数组【11,9,6,4,5,3,2】,添加【8】元素到数组,成【11,9,6,4,5,3,2,8】

构成的树如图所示
heap

  • 插入一个元素可能会破坏原来的堆属性,所以添加完后需要重新调整树结构,以满足堆属性
  • 【8】和【4】节点需要交换,交换后就满足了堆属性,只交换了一次
  • 针对不同的情况交换可能会交换多次才能满足堆属性

heap
交换后的数组为【11,9,6,8,5,3,2,4】

删除

  • 删除任意一个元素,则把删除元素的位置给到末尾元素,再根据堆属性重新调整即可
  • 如上面的【11,9,6,4,5,3,2】,删除【5】节点,然后把末尾节点【2】填上【5】节点的位置上
  • 填上后发现已经满足堆属性了,不需要再调整了
  • 若是填上不满足堆属性的,则需要根据堆属性调整节点的位置

heap