堆的定义:有如下性质的完全二叉树:任意节点X所处的项的关键字大于或等于以X为根的子数中的所有节点出的项的关键字。
意义在于,在数据结构中,其常常被用作优先级队列的结构,其意义是每次从队列中获取的元素,总是最满足某个条件的;比如最大的元素;再例如先进先出队列所满足的特定条件就是,具备放入队列时间最早的那个元素。
堆实现的主要操作就是 插入和 删除(移除并获取那个最符合条件的元素)。先简单描述下逻辑
插入:1. 将新插入的元素,放置到队列的尾部。
2. 若该元素大于其父节点,两个元素互换。(上移操作)
3. 循环第2步,直至该元素没有父节点或小于其父节点。
删除:1. 移掉顶部的节点。
2. 将队末的元素放置到顶部。
3. 该节点与其子节点中较大的那个比较,若小于它,则交换位置,(下移操作)
4. 循环第3步,直到叶节点或不再比其子节点中较大那个小。
若是最小堆,比较都反过来。
在实现的中,用ArrayList作为其内部容器,首先因为ArrayList基于数组,方便快速定位,父节点与子节点的关系只需要计算下就可以得出: 【2*index + 1 】或【 (index -1)/2】, 其次ArrayList以及自动实现了写基础操作,扩容、判空、容器大小等。
public class Heap<T extends Comparable<T>> { ArrayList<T> items; int cursor; //用于计数 public Heap(int size){ items = new ArrayList<T>(size); cursor = -1; } public Heap(){ items = new ArrayList<T>(); cursor = -1; } /** * 上移操作 * @param index 被上移元素的起始位置。 */ void siftUp(int index){ T intent = items.get(index); while(index > 0){ int pindex = (index - 1)/2; T parent = items.get(pindex); if(intent.compareTo(parent) > 0){//上移的条件,比父节点大 items.set(index, parent); index = pindex; }else break; } items.set(index, intent); } /** * 下移操作 * @param index 被下移的元素的起始位置 */ void siftDown(int index){ T intent = items.get(index); int l_index = 2*index +1; while(l_index < items.size()){ T maxChild = items.get(l_index); int max_index = l_index; int r_index = l_index + 1; if(r_index < items.size()){ T rightChild = items.get(r_index); if(rightChild.compareTo(maxChild) > 0){ maxChild = rightChild; max_index = r_index; } } if(maxChild.compareTo(intent) > 0){ items.set(index, maxChild); index = max_index; l_index = index * 2 + 1 ; }else break; } items.set(index, intent); } public void add (T item){ //先添加到最后 items.add(item); //循环上移,以完成重构 siftUp(items.size() -1); } public T deleteTop(){ if(items.isEmpty()){ throw new NoSuchElementException(); } //先获取顶部节点 T maxItem = items.get(0); T lastItem = items.remove(items.size() -1 ); if(items.isEmpty()){ return lastItem; } //将尾部的节点放置顶部,下移,完成重构 items.set(0, lastItem); siftDown(0); return maxItem; } public T next(){ if(cursor < 0 || cursor == (items.size() -1)){ return null; } cursor++; return items.get(cursor); } public T first(){ if (items.size() == 0 ) return null; cursor = 0; return items.get(0); } public boolean isEmpty(){ return items.isEmpty(); } public int size(){ return items.size(); } public void clear(){ items.clear(); } }
转载
相关推荐
数据结构 堆的实现 标准大学额程序 数据结构 堆的实现 标准大学额程序
比较详细地讲述了堆排序的思路和代码实现,适合初学者
主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例,递归详解,二叉查找树和AVL树,堆、散列表和排序以及图论等。对于每一种数据结构的性质和用途,《计算机...
基于python的数据结构代码实现-堆Heap
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
这是我买的一本课程设计案例书上的源代码,上面的案例很经典,特别适合于作 毕业设计的学生使用,当然了,也可以做为做课程设计的学生以参考,希望能给 大家提供帮助!!
这是一个利用堆分配方式实现串的基本操作的小程序,用C++ 写的,欢迎修改指正!
按照算法导论上的伪代码写出的堆数据结构,实现的是最大堆的堆排序
数据结构最大堆的实现,通过改编最小堆的模板,实现最大堆操作。
1.1 针对考研数据结构的代码书写规范以及C 与C 语言基础1 1.1.1 考研综合应用题中算法设计部分的代码书写规范1 1.1.2 考研中的C 与C 语言基础3 1.2 算法的时间复杂度与空间复杂度分析基础 12 1.2.1 考研中的算法时间...
数据结构堆排序的java算法实现,里面用java语言实现了堆排序的算法实现,有输入和输出结果
1、采用堆分配存储建立一个串,并实现串的赋值、比较、联结、求子串、求串的长度、串复制等基本操作。 2、串的模式匹配
数据结构中的堆排序,利用C语言实现,在VC++6.0环境下实现。
这些代码主要是针对严蔚敏老师的《数据结构》一书中的大部分伪代码编辑的代码,能够正常运行,是基于C++编写的代码,包括,数组线性表,链表线性表、双向链表、顺序栈、链栈、链队列,顺序队列,循环队列、KMP算法、...
编写一个程序,实现求串长length_str、串连接、串比较、求子串、串插入、串删除操作。
本程序实现了数据结构课本中几种典型的内部排序方法,包括插入排序、shell排序、冒泡、快速、简单选择、堆排序几种基本的排序方法。
数据结构数据结构-C ++实现C ++模板实现常用数据结构,包括向量,链表,栈,数量,二叉树,二叉搜索树,平衡二叉树,优先权(堆),图,排序算法等。 《数据结构与算法实战》,课程可在该链接查看: : 。本仓库代码...
数据结构 堆的泛型实现,可以支持对的各种操作(包括建堆,弹出,插入,取顶,删除堆中的某一个元素)等等,同时可以传入函数对象定义大顶/小顶堆(默认小顶),使用更灵活!
\数据结构flash演示\版本2\2.3 线性表的链式表示和实现-双向循环链表中右边插入节点.swf \数据结构flash演示\版本2\2.3 线性表的链式表示和实现-双向循环链表中左边插入节点.swf \数据结构flash演示\版本2\2.3 ...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!