本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考,具体如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
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程序设计有所帮助。
原文链接:http://blog.csdn.net/earbao/article/details/46275845