首页 > 代码库 > 哈希表、堆排序
哈希表、堆排序
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。（Java中的实现可以基于数组，把一个数据项的关键字映射成数组下标）
1.开放地址法
若数据不能直接放在由哈希函数计算出来的数组下标所指的单元时，就要寻找数组的其他位置。开放地址法有三种常用的方法：线性探测(+1)、二次探测(+1^2,+2^2...)、再哈希法(使用哈希函数生成步长s,探测序列是+s,+2s,+3s...)
在线性探测中步长总是1,容易产生‘首次聚集’,而二次探测消除了首次聚集但是可能产生二次聚集。
开放地址法中的最大装填因子应该在0.5附近，当装填因子接近1时，查找时间趋于无线(指数级增长)
2.链地址法
在开放地址中，通过在哈希表中再寻找一个空位解决冲突的问题。另一个方法是在哈希表的每个单元设置链表。某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加入到链表中，不需要在原始的数组中寻找空位。链地址法装填因子为1比较合适,链地址法探测的长度随着装填因子变大而线性增长。
堆（heap)，是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构(堆是一种ADT,即抽象数据类型，通常用来实现优先级队列)。
堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质：
(1)任意节点大(小)于它的所有后裔，最大(小)元在堆的根上（堆序性）。
(2)堆总是一棵完全树。
(3)堆通常用一个数组实现。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆是一种二叉树，二叉树的层数L=log2(N+1)，其中N为节点数。向下移动元素和向上移动元素的循环执行了L-1次，所以这两种操作执行的时间和log2N成正比，因此可以认为堆操作的时间复杂度都是O(logN),每个方法都要执行N次，所以整个操作需要O(N*logN)时间
堆排序
heapSort最朴素的思想是使用insert()方法在堆中插入全部的无序的数据项，然后重复用remove()例程，就可以按序移除所有数据项。insert()和remove()的复杂度都是O(logN)的，且每个方法都要执行N次，所以整个排序需要O(N*logN)时间。
可以分别在时间和空间上做一些改进。
时间：不采用insert每个元素的方式，而是通过对N/2-1节点开始一直到根节点为止调用trickleDown方法把一个无序数组变成堆。这样就避免了调用上移函数N次，而只是调用了下移函数N/2次
空间：使得堆和初始数组使用同一个数组而不需要使用额外的空间。
堆排序的效率：O(N*logN)
尽管比快速排序略慢，但是它比快速排序的优点是对初始数据的分布不敏感。在关键字按某种排列顺序的情况下，快速排序的时间复杂度可以降到O(N平方级)，然而堆排序对任意排列的数据，其排序时间都为O(N*logN)
1.开放地址法
若数据不能直接放在由哈希函数计算出来的数组下标所指的单元时，就要寻找数组的其他位置。开放地址法有三种常用的方法：线性探测(+1)、二次探测(+1^2,+2^2...)、再哈希法(使用哈希函数生成步长s,探测序列是+s,+2s,+3s...)
在线性探测中步长总是1,容易产生‘首次聚集’,而二次探测消除了首次聚集但是可能产生二次聚集。
开放地址法中的最大装填因子应该在0.5附近，当装填因子接近1时，查找时间趋于无线(指数级增长)
2.链地址法
在开放地址中，通过在哈希表中再寻找一个空位解决冲突的问题。另一个方法是在哈希表的每个单元设置链表。某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中。其他同样映射到这个位置的数据项只需要加入到链表中，不需要在原始的数组中寻找空位。链地址法装填因子为1比较合适,链地址法探测的长度随着装填因子变大而线性增长。
堆（heap)，是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构(堆是一种ADT,即抽象数据类型，通常用来实现优先级队列)。
堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质：
(1)任意节点大(小)于它的所有后裔，最大(小)元在堆的根上（堆序性）。
(2)堆总是一棵完全树。
(3)堆通常用一个数组实现。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆是一种二叉树，二叉树的层数L=log2(N+1)，其中N为节点数。向下移动元素和向上移动元素的循环执行了L-1次，所以这两种操作执行的时间和log2N成正比，因此可以认为堆操作的时间复杂度都是O(logN),每个方法都要执行N次，所以整个操作需要O(N*logN)时间
堆排序
heapSort最朴素的思想是使用insert()方法在堆中插入全部的无序的数据项，然后重复用remove()例程，就可以按序移除所有数据项。insert()和remove()的复杂度都是O(logN)的，且每个方法都要执行N次，所以整个排序需要O(N*logN)时间。
可以分别在时间和空间上做一些改进。
时间：不采用insert每个元素的方式，而是通过对N/2-1节点开始一直到根节点为止调用trickleDown方法把一个无序数组变成堆。这样就避免了调用上移函数N次，而只是调用了下移函数N/2次
空间：使得堆和初始数组使用同一个数组而不需要使用额外的空间。
堆排序的效率：O(N*logN)
尽管比快速排序略慢，但是它比快速排序的优点是对初始数据的分布不敏感。在关键字按某种排列顺序的情况下，快速排序的时间复杂度可以降到O(N平方级)，然而堆排序对任意排列的数据，其排序时间都为O(N*logN)
哈希表、堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。