服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|JavaScript|易语言|

服务器之家 - 编程语言 - JAVA教程 - Java基于堆结构实现优先队列功能示例

Java基于堆结构实现优先队列功能示例

2021-02-07 17:30yunshouhu JAVA教程

这篇文章主要介绍了Java基于堆结构实现优先队列功能,结合实例形式分析了java优先队列的简单定义与使用方法,需要的朋友可以参考下

本文实例讲述了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基于堆结构实现优先队列功能示例

希望本文所述对大家java程序设计有所帮助。

原文链接:http://blog.csdn.net/earbao/article/details/46275845

延伸 · 阅读

精彩推荐