新入公司，管理比较严，机子上还没任何开发装备，不让自己装，没有权限，连个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-
相关推荐
优先队列是一种特殊的数据结构，它允许我们按照...总的来说，这个压缩包提供了一个用C语言实现的基于堆的优先队列，包含了实现和测试的源码，以及使用说明，是学习和理解优先队列及其底层数据结构堆的一个实用资源。
优先队列是一种特殊的数据结构，它允许我们快速访问或删除具有最高优先级的元素。在计算机科学中，优先队列通常用作...理解堆和优先队列的工作原理对于深入学习数据结构和算法至关重要，也是提升编程能力的重要一步。
在广东工业大学的教程中，优先队列和二叉堆是数据结构的重要组成部分。优先队列是一种特殊的队列，其元素具有优先级属性...通过优先队列的学习，学生可以更好地掌握数据组织和算法设计的方法，提高解决复杂问题的能力。
这些特性使得堆成为实现优先队列的理想选择。 **大根堆与小根堆** 大根堆和小根堆是堆的两种基本类型。大根堆中，根节点总是集合中最大（或最小）的元素，确保了在任何时候，堆顶的元素都是最大的。相反，小根堆的...
总之，`PriorityQ.java`文件可能是一个简单的数组实现优先队列的示例，通过分析这个文件，我们可以学习到如何利用数组数据结构实现优先队列，以及理解其核心的插入、删除和查找操作。同时，这也能帮助我们更好地掌握...
- 自定义优先队列可能涉及到堆的实现，例如最小堆或最大堆，或者使用其他数据结构如平衡搜索树（AVL、红黑树等）。 - 需要实现插入、删除、查找和更新等操作，同时确保操作的时间复杂度尽可能低，通常是O(log n)。...
在压缩包文件"**c#优先队列实现**"中，很可能包含了这四种实现的代码示例，你可以通过查看这些文件学习每种实现的具体细节，比如如何定义优先级、如何进行插入和删除操作，以及它们在不同场景下的性能表现。...
在本文中，我们将深入探讨基于VC的堆和最大优先队列的实现，这些实现是通过C++编程语言完成的。堆是一种特殊的树形数据结构，它满足特定的性质，如最大堆或最小堆，常被用于优化算法和解决各种问题。在VC（Visual ...
通过本文的学习，我们了解了STL中优先队列的基本概念及其使用方法，并且掌握了如何通过自定义比较器和使用内置比较器实现逆序排列。优先队列作为一种高效的数据结构，在实际编程中有着广泛的应用，掌握其使用方法...
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
本项目采用小大根交替堆来实现双端优先队列，这在处理学生成绩查询等场景中具有实际应用价值。下面我们将详细探讨小大根交替堆及其在双端优先队列中的实现。 首先，让我们了解小大根交替堆的概念。小大根交替堆是一...
通过本文的学习，我们不仅了解了优先队列的基本概念及其在C++中的实现方法，还学习了如何自定义比较器来满足特定的需求。同时，我们也简单介绍了贪心算法，并探讨了它与优先队列之间的联系。这些知识将在未来的算法...
"优先队列及其应用" 优先队列（Priority Queue）是一种特殊的队列，出队列的顺序由元素的优先级决定。它是一种抽象数据类型（Abstract Data Type），定义了一些基本操作，如创建、插入、删除等。 基本概念： 1. ...
在C#编程中，泛型优先队列是一种特殊的数据结构，它结合了队列和堆的概念，用于存储具有优先级的元素。...通过学习和理解这些内容，开发者可以深入掌握如何在C#中利用泛型和堆数据结构来创建和使用优先队列。
在这个场景中，我们关注的是一个基于最大堆实现的最大优先队列。最大堆是一种完全二叉树，其中每个父节点的值都大于或等于其子节点的值，这样确保了根节点始终是堆中最大的元素，即具有最高优先级的元素。 首先，让...
优先队列通常用堆数据结构实现，如最小堆或最大堆。最小堆确保每次取出的都是当前堆中最小的元素，而最大堆则取出最大的元素。堆是一种完全二叉树，满足堆属性：父节点的值要么小于等于（最小堆）或大于等于（最大堆...
根据提供的文件信息，可以看出这是一段与加密技术相关的C++代码片段，主要涉及到了优先队列的概念并未在代码中直接体现出来。...此外，深入学习不同的优先队列实现方法也有助于提高编程能力和解决问题的能力。
优先队列是一种特殊的数据结构，它在处理问题时具有较高的效率，特别是在需要频繁进行查找最大或最小元素并删除这些...通过学习这部分内容，你可以深入理解优先队列的工作原理，提高在算法设计和数据结构使用上的能力。
【优先队列】是计算机科学中一种特殊类型的队列，其主要特征...总之，这个实验是学习和理解优先队列的重要实践，通过动手操作，学生能更好地掌握优先队列的内在逻辑和应用，提升在实际问题中解决复杂数据处理的能力。