本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考,具体如下:
package Demo; import java.util.NoSuchElementException; /* * 小顶堆 java使用堆结构实现优先队列 */ public class JPriorityQueue<E> { @SuppressWarnings("hiding") class QueueNode<E> { int capacity; int size; E[] queue; QueueNode(int capacity) { this.capacity = capacity; } } QueueNode<E> node; public void print() { E[] objs=this.node.queue; for(int i=0;i<this.node.size;i++) { System.out.print(objs[i]+" "); } System.out.println(); } @SuppressWarnings("unchecked") public JPriorityQueue(int capacity) { node = new QueueNode<E>(capacity); node.size = 0; node.queue = (E[]) new Object[capacity + 1]; } public void add(E x) { int k = node.size; while (k > 0) { int parent = (k - 1) / 2; E data = node.queue[parent]; @SuppressWarnings({ "unchecked", "rawtypes" }) Comparable<E> key = (Comparable) x; if (key.compareTo(data) >= 0) break; node.queue[k] = data; k = parent; } node.queue[k] = x; node.size++; } public E remove() { int parent = 0; if (node.size == 0) { throw new NoSuchElementException("queue is null"); } E min = node.queue[0];// top E last = node.queue[node.size - 1];// last node.queue[0] = last;// add the last to top node.queue[node.size - 1] = null; node.size--; @SuppressWarnings("unchecked") Comparable<? super E> complast = (Comparable<? super E>) last; if (node.size == 2 && complast.compareTo(node.queue[1]) > 0) { // 只剩下最后两个结点,进行比较 node.queue[0] = node.queue[1]; node.queue[1] = last; } if (node.size > 2) { // 大于三个结点的,向下旋转 while (parent < node.size / 2) { int left = 2 * parent + 1;// left child int right = left + 1;// right child E root = node.queue[parent]; @SuppressWarnings("unchecked") Comparable<? super E> comproot = (Comparable<? super E>) root; if (comproot.compareTo(node.queue[left]) < 0 && comproot.compareTo(node.queue[right]) < 0) break; @SuppressWarnings("unchecked") Comparable<? super E> compleft = (Comparable<? super E>) node.queue[left]; if (compleft.compareTo(node.queue[right]) <= 0) { node.queue[parent] = node.queue[left]; node.queue[left] = root; parent = left; } else { node.queue[parent] = node.queue[right]; node.queue[right] = root; parent = right; } if (right * 2 >= node.size) break; } } return min; } public static void main(String[] args) { System.out.println("小牛知识库测试结果:"); JPriorityQueue<String> queue = new JPriorityQueue<String>(10); queue.add("Z"); queue.add("B"); queue.add("QZA"); queue.add("QBA"); queue.add("EAA"); queue.add("A"); queue.print(); // queue.remove(); // queue.remove(); // queue.remove(); // queue.remove(); // queue.remove(); System.out.println(queue.remove()); System.out.println(queue.remove()); System.out.println(queue.remove()); System.out.println(queue.remove()); System.out.println(queue.remove()); System.out.println(queue.remove()); } }
运行结果:
更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
我正在编写一个涉及堆实现的代码,在我的bubbleUp方法中,在我的while循环行中,我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题,但解决这个问题的最佳方法是什么?我在实现removeHigh方法时也遇到了一些问题,该方法旨在从队列中移除最高的元素。
我目前正在尝试实现min heap PQ,但是我在实现的正确性方面遇到了一些问题,我似乎无法找出我做错了什么——它没有输出最低优先级,也没有对它们进行正确排序。 使用以下测试数据: 我得到以下结果: 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子,但最后一个输出是最大的优先级,所以这没有意义。我花了几个小时试图研究堆优先级队列,但我找不到任何帮助。 以下是CMP要求的更好的代码
在前面的部分中,你了解了称为队列的先进先出数据结构。队列的一个重要变种称为优先级队列。优先级队列的作用就像一个队列,你可以通过从前面删除一个项目来出队。然而,在优先级队列中,队列中的项的逻辑顺序由它们的优先级确定。最高优先级项在队列的前面,最低优先级的项在后面。因此,当你将项排入优先级队列时,新项可能会一直移动到前面。我们将在下一章中研究一些图算法看到优先级队列是有用的数据结构。 你可能想到了几种
注意:我知道可以用比较器创建优先级队列,然后重复调用Add。
简介 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (largest-in,first-out)的行为特征。 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有: 查找; 插入一个新元素; 删除。 在最小优先队列(min priority qu
1)insert(name,priority):这个函数应该取一个string类型的名称和一个integer类型的优先级,并将它们插入到优先级队列中。remove():这个函数应该移除具有最高优先级值的对象,并从对象中返回名称字符串。 2)作为背景,我有三个类用于这个程序:第一,包含读取文件和使用函数的实现的“main”类。第二,“name”类,它创建包含名称字符串和优先级int的name对象、一