堆的性质是什么?怎么实现堆?
堆的性质:
- 堆在逻辑上是一棵完全二叉树
- 堆是基于数组实现的,堆的所有元素都存储在数组中
- 满足任意结点的值都大于其子树中结点的值的堆,称为大堆
- 满足任意结点的值都小于其子树中结点的值的堆,称为小堆
- 堆的基本作用是快速的在集合中找到最值
堆的实现(小堆为例):
堆的向下调整(siftDown):为了满足小堆的性质,即任意结点的值都小于其子树中结点的值,因此需要对指定结点进行向下调整,代码如下:
成都创新互联服务项目包括丰镇网站建设、丰镇网站制作、丰镇网页制作以及丰镇网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,丰镇网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到丰镇省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
//size是数组的大小,index是需要向下调整的元素的下标 public void siftDown(int[] array, int size, int index) { int left = (index << 1) + 1; //堆是完全的二叉树,如果没有左节点,那么必定没有右节点,因此以左节点作为先决条件 while(left < size) { //先假定最小的值时左节点的值 //原因:进入循环左节点必定存在,然后再判断右节点是否存在, //不存在的话最小值肯定是左节点,如果存在的话,只有当右节点的值小于左节点时才会让最小值时右节点的值 int min = left; int right = (index << 1) + 2; //只有右节点存在且小于左节点的值时才进入循环 if(right < size && array[right] < array[left]) { min = right; } //如果两子节点中的最小值都大于他本身的值时,调整结束 if(array[min] >= array[index]) { break; } //交换指定节点和其子节点中最小值的节点 int tmp = array[index]; array[index] = array[min]; array[min] = tmp; //调整后下标是min的结点等待继续调整 index = min; left = (index << 1) + 1; } }
- 构建堆(heapify):从最后一个非叶子结点开始向下调整直到根节点(下标为0的元素)后,表示任意结点都满足了小堆的性质,实现方式如下:
//此处size是数组最后一个元素的下标 public void heapify(int[] array, int size) { for (int i = (size - 1) >> 1; i >= 0; i--) { new SiftDown().siftDown(array, size, i); } }
3.下述为PriorityQueue在构建堆时的源码:
//其中size表示的是数组中元素的个数,因此和上面构建代码中的循环条件有所差别,但是本质表达的是一个意思 private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); }
堆最常解决的问题:
- TopK问题
- 排序问题
堆的应用—优先级队列:
- 提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
- 优先级队列的实现方式有很多,但是最常见的是使用堆来构建
- Java中的优先级队列就是通过构建堆来实现的
分享名称:堆的性质是什么?怎么实现堆?
文章URL:http://scyanting.com/article/ghiipg.html