新入公司，管理比较严，机子上还没任何开发装备，不让自己装，没有权限，连个jar包都不让download，没事可做，闲得蛋疼，故作此篇。。。
介绍一个在线编译工具：http://www.compileonline.com/compile_java_online.php
转入正题（本文参考：http://jiangzhengjun.iteye.com/blog/565275，然后按照自己理解重新把code做了一遍。在下对该篇博主加了关注。）
堆的定义
参考：http://zh.wikipedia.org/wiki/%E5%A0%86_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)
堆（英语：heap)亦被称为：优先队列（英语：priority queue），是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因而实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构，实质上堆可用来实现优先级队列，或者说堆就是一种优先级队列。
再看看优先队列：普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征，一般普通的队列添加是在最后加入，但优先级队列却不一定添加到最后，它会按照优先级算法把它插入到队列当中去，出队时还是从第一个开始，即取根元素，这样保证了队列中优先级高的先服务，而不是先来先服务了。至于优先级算法如何得出最高权限完全是根据需要自定义。
看一个优先队列的实现代码：
package org.oham.priorityqueue;
import java.util.ArrayList;
import java.util.ListIterator;
public class ArrayListPriorityQueque<T extends Comparable<T>> {
private ArrayList<T> list;
public ArrayListPriorityQueque() {
this.list = new ArrayList<T>();
}
/**
* 此处权限规则为元素compare后最小的权限最高，排在队列第一。
*/
public void add(T elem) {
//此处判断若队列为空，则直接添加，或则比较队列最后元素，即权限最低者，若新加的元素较之
//权限更低，则直接添加
if (list.isEmpty() || elem.compareTo(list.get(list.size() - 1)) >= 0) {
list.add(elem);
} else {
ListIterator<T> iterator = list.listIterator();
//逐个遍历元素，取之判断，发现新添元素较之权限低，则添加到该元素其后
while (iterator.hasNext() && elem.compareTo(iterator.next()) >= 0)
;
iterator.previous();
iterator.add(elem);
}
}
public T getMin() {
if(list.size() == 0) throw new NullPointerException("queque is empty");
return list.get(0);
}
public T gremoveMin() {
if(list.size() == 0) throw new NullPointerException("queque is empty");
return list.remove(0);
}
public ArrayList<T> getList() {
return list;
}
}
测试代码：
public void testQueue() {
Integer [] arr = {21, 43, 23, 67, 20, 63, 89};
ArrayListPriorityQueque<Integer> priorityQueue = new ArrayListPriorityQueque<Integer>();
for(Integer i : arr) {
priorityQueue.add(i);
}
Iterator<Integer> it = priorityQueue.getList().iterator();
while(it.hasNext()) {
System.out.print(it.next() + "-");
}
}
输出 结果：
20-21-23-43-63-67-89-
JDK1.5以后有了PriorityQueue的实现，此处的代码根本无法比拟，只是说明概念而已。
关于堆的逻辑定义如下：
个元素序列{k1,k2...ki...kn},当且仅当满足下列关系时称之为堆：
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
这里的意思是，堆是一个完全二叉树，它是一棵空树或根元素大于左右子节点（这时叫大顶堆）并且左右子节点又是堆。
关于完全二叉树（参考：http://baike.baidu.com/view/427107.htm），若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树特点
叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构为:var tree:array[1..n]of longint;{n:integer;n>=1}。
对于tree有如下特点：
（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；
（3）若i>1，tree的双亲为tree[i / 2]；
（4）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；
（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。
根据对的特点，堆的添加元素与删除元素时都会破坏堆结构，所以添加与删除进都要进行结构调整。
再次声明JDK1.5后已经有了heap的实现，此处代码不能同日而语，而且在下直觉认为，下面实现有Bug，请慎读，不过此处目的只为阐述概念性的东西。
堆的实现代码：（有关二叉树，可以参考在下一篇笔记：http://gwoham-163-com.iteye.com/blog/1896260）
package org.oham.priorityqueue;
import java.util.*;
public class Heap<T extends Comparable<T>> {
private T[] heap;
private int size;
private int initCapacity = 9;
private Comparator<T> comparator;
public Heap() {
heap = (T[]) new Comparable[initCapacity];
}
// 允许自定义优先级判定规则
public Heap(Comparator<T> comparator) {
this.comparator = comparator;
heap = (T[]) new Comparable[initCapacity];
}
public T[] getHeap() {
List<T> list = new ArrayList<T>();
for (T e : heap) {
if (e != null) {
list.add(e);
}
}
T[] result = (T[]) new Comparable[list.size()];
//heap = list.toArray(result);
return list.toArray(result);
}
// 排序，传入一个数组,使其具有堆的数据结构, 这里的排序顺便用
// 目标数组的元素构建了heap，便于测试而已，实际不应这样做
public void heapSort(T[] elems) {
if (elems == null)
throw new NullPointerException();
for (int i = 0; i < elems.length; i++) {
if (elems[i] == null)
throw new NullPointerException(
"Target array not allow contain null elements");
}
heap = (T[]) new Comparable[initCapacity];
size = 0;
for (T elem : elems) {
add(elem);
}
System.arraycopy(heap, 0, elems, 0, elems.length);
}
// 添加元素
public void add(T elem) {
//此处heap到底能不能添加null元素有待商量，在下认为不影响优先级规则应该是可以的，
//不行就看看下面的remove方法，只是。。。
//不知道如何处理null的元素，所以干脆抛了个null pointer。
if(elem == null)
throw new NullPointerException("Can not add null element to heap");
// 判断放入元素后是否满，若满则先扩充容量(此处建议看看ArrayList的源码，有类似的)
if (size++ == heap.length) {
T[] newHeap = (T[]) new Comparable[2 * heap.length];
System.arraycopy(heap, 0, newHeap, 0, size - 1);
heap = newHeap;
}
heap[size - 1] = elem;
adjustUp(); //添加后堆规则可能打破，所以需重新调整堆结构
}
//添加元素后向上调整堆结构，构造小顶堆，即添加的小的元素向上(根)浮
//示意图：
/* 添加13 13小于56，交换
* → 8 → 8
* / \ / \
* 32 11 32 11
* / \ / \ / \ / \
* 37 56 88 50 37 (13) 88 50
* / \ / \ / \ / \
* 43 77 89 (13) 43 77 89 (56)
*
* 现13小于32，还需交换 现13大于8，所以调整完成
* → 8
* / \
* (13) 11
* / \ / \
* 37 (32) 88 50
* / \ / \
* 43 77 89 56
*
*/
private void adjustUp() {
int childNum = size;
while (childNum > 1) {
int parentNum = childNum / 2;
if (compare(heap[childNum - 1], heap[parentNum - 1]) >= 0)
break;
T tmp = heap[parentNum - 1];
heap[parentNum - 1] = heap[childNum - 1];
heap[childNum - 1] = tmp;
childNum = parentNum;
}
}
//删除元素
public void remove(T elem) {
int pos = returnElementPosByLevel(elem);
if (pos != -1) {
heap[pos - 1] = heap[size - 1];
adjustDown(pos); //堆结构调整，从指定的节点向下开始调整
// 此处可以考虑重新构造heap数组，不加null元素，
// 若像如下做法实在跟add方法不好对应，
// 只是重新构造数组又对不起性能开销。恳请高招。。。
heap[--size] = null;
}
}
//堆结构调整，从指定的节点向下开始调整
//示意图：
/* 删除12 最后元素56移至12
* → 8 → 8
* / \ / \
* (12) 11 (56) 11
* / \ / \ / \ / \
* 37 32 88 50 37 32 88 50
* / \ / \ / \ /
* 43 77 89 56 43 77 89
*
* 现56大于最小节点32，需交换 堆结构恢复，调整结束
* → 8
* / \
* (32) 11
* / \ / \
* 37 (56) 88 50
* / \ /
* 43 77 89
*
*/
private void adjustDown(int pos) {
int parentNum = pos;
while (parentNum < size) {
int childNum = 2 * parentNum;
int minChildNum = parentNum;
if (childNum < size
&& compare(heap[childNum - 1], heap[parentNum - 1]) <= 0) {
minChildNum = childNum - 1;
}
if (childNum + 1 <= size
&& compare(heap[childNum], heap[childNum - 1]) <= 0) {
minChildNum = childNum + 1;
}
if (parentNum != minChildNum) {
T tmp = heap[parentNum - 1];
heap[parentNum - 1] = heap[minChildNum - 1];
heap[minChildNum - 1] = tmp;
parentNum = minChildNum;
} else {
break;
}
}
}
//获取目标元素在的堆的序号（亦可看作优先级标注，此处越小优先级越高）
//若找不到元素，返回-1
//此处用了二叉树遍历算法（前序）
public int returnElementPosByLevel(T elem) {
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
while(!stack.isEmpty()) {
int pos = stack.pop();
if( compare(heap[pos-1], elem) == 0) {
return pos;
}else {
if(pos*2 + 1 <= size) {
stack.push( pos*2+1 );
}
if(pos*2 <= size) {
stack.push(pos*2);
}
}
}
return -1;
}
//遍历指定元素的以及其下的所有子孙元素（前序）
public void levelTraversal(T elem) {
if (size == 0)
return;
int pos = returnElementPosByLevel(elem);
if (pos == -1)
return;
//这是递归的实现
/*System.out.print(elem + "-");
if(pos*2 <= size) {
int leftChildElem =
pos * 2; levelSort(heap[leftChildElem-1]);
}
if(pos*2+1 <= size) {
int rightChildElem = pos * 2 + 1;
levelSort(heap[rightChildElem-1]);
}*/
//这是非递归的实现
LinkedList queue = new LinkedList();
queue.add(pos);
while (!queue.isEmpty()) {
int num = (Integer) queue.removeFirst();
System.out.print(heap[num - 1] + "-");
if (num * 2 <= size) {
queue.add(num * 2);
if (num * 2 + 1 <= size) {
queue.add(num * 2 + 1);
}
}
}
}
public void layerTraversal() {
}
private int compare(T srcElem, T trgElem) {
return (comparator == null ? srcElem.compareTo(trgElem) : comparator
.compare(srcElem, trgElem));
}
}
测试代码：
public void testHeap() {
Integer[] preArr = { 12,32,50,37,8,88,11,43,77,89,56};
Heap<Integer> heap = new Heap<Integer>();
//对原始数组进行堆排序，顺便用原始数组初始化此处的heap，便于测试
heap.heapSort(preArr);
System.out.print("Sort option : ");
for(Integer i : preArr) {
System.out.print(i + "-");
}
System.out.println();
//对堆的删除元素操作
heap.remove(12);
Comparable[] arr1 = heap.getHeap();
System.out.print("Remove 12 option : ");
for(int i=0; i<arr1.length; i++) {
System.out.print(arr1[i] + "-");
}
System.out.println();
//对堆的添加元素操作
heap.add(13);
Comparable[] arr2 = heap.getHeap();
System.out.print("Add 13 option : ");
for(int i=0; i<arr2.length; i++) {
System.out.print(arr2[i] + "-");
}
System.out.println();
//对堆的遍历操作
System.out.println("Element 88's position: " +heap.returnElementPos(88));
System.out.println("Element 89's position: " +heap.returnElementPos(89));
System.out.println("Element 100's position: " +heap.returnElementPos(100));
System.out.print("Level Traversal element 11: ");
heap.levelTraversal(11);
System.out.println();
//删除根元素试试
heap.remove(8);
Comparable[] arr3 = heap.getHeap();
System.out.print("Remove root element 8 option : ");
for(int i=0; i<arr3.length; i++) {
System.out.print(arr3[i] + "-");
}
}
运行结果：
Sort option : 8-12-11-37-32-88-50-43-77-89-56- Remove 12 option : 8-32-11-37-56-88-50-43-77-89- Add 13 option : 8-13-11-37-32-88-50-43-77-89-56- Element 88's position: 6 Element 89's position: 10 Element 100's position: -1 Level Traversal element 11: 11-88-50- Remove root element 8 option : 11-13-50-37-32-88-56-43-77-89-
相关推荐
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
使用最大堆实现最大优先队列，采用顺序存储，仅供学习交流
C++ 优先队列 学习和使用实例， 可直接在VC2008下编译运行。
优先队列的二叉堆实现 在前面的章节里我们学习了“先进先出”（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做“优先队列”（Priority Queue）。优先队列的出队（Dequeue）操作和队列一样，都是从队首出队。...
leetcode添加元素使和等于 简单的复杂度分析 O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2) 大O描述的是算法的运行时间和输入数据之间的关系 public static int sum(int[] nums) { ...解释：算法运行时间的多少和nums存在的...
平时⽣活中，我们有时会说⼀堆⼈，⼀堆某某东西，其实数据结构⾥的堆也和⽣活中的类 似，不同的就是数据结构⾥的堆是由⼀些按照某种优先级来组织成的队列，所以堆⼜叫做优先队列，显⽽易见，堆是可以把某种优先级最...
第九章最佳搜索与堆 M.94275.CN 9.1最佳搜索 9.2优先队列 9.3堆 第九章测验 9.5总结 9.4大结局 计算机算法与程序设计(python)-计算机PPT模板全文共34页，当前为第21页。 第九章最佳搜索与堆 第九章编程作业 计算机...
排序与查找：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序、二分查找等。 B站上有许多优秀的UP主分享了这些基础算法和数据结构的讲解视频，学习者可以边看视频边实践，加深理解。 二、进阶算法 在...
包括源码：常用排序算法（插入、堆、归并、快速）、装配线问题、最长公共子序列问题、矩阵连乘问题、 优先队列、huffman编码、贪心算法，全部用Java实现的。 算法导论答案
数据结构：二叉树和一般树、优先队列：堆、左高树、竞赛树、搜索树、图 算法设计方法：贪心算法、分治算法、动态规划、回溯、分支限界等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。 ...
22堆排序与优先队列.pptx 23快速排序.pptx 24归并排序.pptx 25桶基计排序.pptx 26查找概念与顺序查找.pptx 27折半与分块查找.pptx 28二叉查找树.pptx 29哈希概念函数及冲突.pptx 30哈希的应用.pptx 31八数码问题启发...
描述 leetcode问题解决方案的集合。 结构 不。 问题 话题 104 二叉树的最大深度 树，递归 146 设计，双链表，哈希表 ...优先队列/堆 973 K个最接近原点的 优先队列/堆 MISC 要学习间隔重复技
B 优先队列 A 特里树 A 树 A 二叉搜索树 A AVL树 A 红黑树 A 线段树- 带有最小/最大/总和范围查询示例 A Fenwick 树（二元索引树） A 图（有向图和无向图） A 不相交集- 联合查找数据结构或合并查找集 A 布隆
书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书适合作为计算机相关专业本科生的数据结构课程和研究生算法分析...
22堆排序与优先队列.pptx 23快速排序.pptx 24归并排序.pptx 25桶基计排序.pptx 26查找概念与顺序查找.pptx 27折半与分块查找.pptx 28二叉查找树.pptx 29哈希概念函数及冲突.pptx 30哈希的应用.pptx 31八数码问题启发...
第三部分“排序”（第6～11章）按章节顺序分别讨论了基本排序方法（如选择排序、插入排序、冒泡排序、希尔排序等）、快速排序方法，归并和归并排序方法、优先队列与堆排序方法、基数排序方法以及特殊目的排序方法，...
树的删除.swfB树的生成.swf查找中序线索二叉树后继.swf串的顺序存单链表结点的插入.swf单链表结点的删除.swf堆排序.swf二叉排序树的删除.swf二叉排序树的生成.swf二叉树的建立.swf二分查找.swf分块查找.swf构造...
第1章 欢迎学习《玩转数据结构》 第2章 不要小瞧数组 第3章 栈和队列 ...第8章 优先队列和堆 第9章 线段树 第10章 Trie 第11章 并查集 第12章 AVL 第13章 红黑树 第14章 哈希表 链接永久有效，若是有问题请留言
【算法日积月累】9-堆与优先队列 （同上） 【算法日积月累】10-堆排序、heapify、原地堆排序 （同上） 【算法日积月累】11-索引堆 （同上） 第 3 部分：二分查找法与二分搜索树 【算法日积月累】12-二分查找法 ...
- [5-3 二叉堆](5.3_binaryHeap.py) - [5-4 二叉搜索树](5.4_binarySearchTree.py) - [5-5 平衡二叉树](5.5_avlTree.py) - [5-6 红黑树](5.6_rbTree.py) - [5-7 trie](5.7_trie.py) - [5-8 双数组字典树](5.8_datree...