数据结构第五讲:树(下)

5.1 堆

什么是堆

最大堆的插入

思路:

  1. 将插入值放到末尾
  2. 比较其于父结点的大小关系,如果大于父结点,则交换位置,循环往复直至root,小于则直接停止。

用完全二叉树可以直接定位父结点下标

最大堆的删除

思路:

  1. 删除root,同时将二叉树最后一个结点放到root补位
  2. 取其左右儿子中大的和其进行比较,如果大于则交换位置,循环往复直至叶结点,不然直接停止。

最大堆的建立

方法一:

复杂度[TBC]

方法二思路:

  1. 从最后一个非叶子结点开始,把这颗子树调成一个堆,循环往复,直到root。

每个非叶子结点的调整过程最坏情况下挪动元素次数是它的高度。因此建堆时,最坏情况下需要挪动元素次数是等于树中各结点的高度和

5.2 哈夫曼树与哈夫曼编码

什么是huffman树

huffman树的构造

[TBC]如何利用堆构造、复杂度?

huffman编码

5.3 集合及运算

集合的表示

并查集

5.4 小白专场:堆中的路径