算法与数据结构学习笔记(6)

1、散列表

使用散列值作为索引存储数据,若散列函数实现得好,效率可接近O(1)。

处理散列碰撞的方法:

  • 线性跳跃:H1(N)+n
  • 平方跳跃:H1(N)+n2
  • 二次散列:H1(N)+n*H2(N)
  • 在内部使用链表(较简单,但性能会轻微下降)

(H1、H2为散列函数,N为数据,n为碰撞次数)

H2(N)必须与散列表大小互质,否则遇到多次碰撞时会陷入死循环。最简单的方法为确保散列表的大小为质数。

非链表实现的散列表的装入率(Load Factor)超过约三分之二时性能会大大下降。

链表实现的散列表装入率为1.0以下时性能最佳,在高装入率时的性能下降速度也比非链表实现慢,所以在数据量未知的情况下较为适合。

2、堆

堆的内部为一棵完整二叉树,其基本特征为:父节点的数据一定大于(或小于)子节点的数据。堆的基本操作有插入和删除,时间复杂度均为O(log N)。

插入:把新节点放置在完整二叉树的尾部,然后上移(trickle up)到适当位置。

删除:保存二叉树的根节点数据,用二叉树的尾部节点替换根节点,再下移(trickle down)到适当位置(在下移时需要同时比较左子节点和右子节点,否则会破坏基本特征),最后返回保存的数据。

由于删除时返回的数据必定为堆内最大(或最小)的数据,而且时间复杂度比有序数组低,所以堆适合作为优先队列的内部结构。

堆排序:把所有数据插入堆,再取出即可。时间复杂度为O(N log N),但比快速排序慢。

提高堆排序的效率:由于对两个子节点为有效堆的节点进行下移后能得到一个有效堆(参考删除操作),所以可以把数组看成一棵二叉树,从底部的非叶节点开始(叶节点可视作一个有效堆),由右到左从下至上进行下移操作,完成后整个数组即成为一个有效堆。

Leave a Reply

Your email address will not be published. Required fields are marked *