DATE:2013-8-4
-------------------------------
一.堆的特点:
A)它是完全二叉树
B)一般情况下,用数组实现
C)堆中的每一节点都满足堆的条件(每一节点的关键字都大小或等于子节点的关键字)
D)相对于二叉搜索树,它是弱序的
E)节点索引下标:
》父节点下标:(index-1)/2
》左子节点:2*index + 1
》右子节点:2*index + 2
二、用堆实现的优先队列
1、前提
2、关键算法:
A)向上筛选(插入)
int parent = (index-1) / 2;
Node bottom = heapArray[index];
while( index > 0 && //向上寻找合适的位置
heapArray[parent].getKey() < bottom.getKey() )
{
heapArray[index] = heapArray[parent]; // move it down
index = parent;
parent = (parent-1) / 2;
} // end while
heapArray[index] = bottom;//找到了合适的插入位置
B)向下筛选(移除、排序)
int largerChild;
Node top = heapArray[index]; // save root
while(index < currentSize/2) // while node has at
{ // least one child,
int leftChild = 2*index+1;
int rightChild = leftChild+1;
// find larger child
if(rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() <
heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if( top.getKey() >= heapArray[largerChild].getKey() )
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // go down
} // end while
heapArray[index] = top;
3、优缺点:相对于快速排序,略慢;但它对初始数据的分布不敏感
4、效率:O(N*logN)
分享到:
相关推荐
中软国际培训的学习笔记,很值得参考。学习java数据结构很有必要看看
Java数据结构和算法第十二讲.avi Java数据结构和算法第十五讲.avi Java数据结构和算法第十八讲.avi Java数据结构和算法第十六讲.avi Java数据结构和算法第十四讲.avi Java数据结构和算法第十讲.avi Java数据结构和...
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
Java数据结构和算法学习笔记,对于爱好Java人员来说,再好不过了
这是我从B站上看韩老师讲的数据结构与算法后整理的笔记 代码经过运行,欢迎批评指正 有些地方我感觉还是挺难的 大都经过我自己的语言进行描述,韩老师中期的表达可能或多或少也影响可阅读性,望先生们见谅
Java数据结构和算法.pdf
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
sgg数据结构和算法笔记
java 数据结构和算法, 排序算法, 数组,链表,二叉树
数据结构、算法
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
包含Java数据结构和算法(第二版)书中每章节源代码
Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法Java数据结构与算法
《Java数据结构与算法》中的示例applet,很完整很全面,方便大家交流学习