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

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

服务器之家 - 编程语言 - Java教程 - java编程实现优先队列的二叉堆代码分享

java编程实现优先队列的二叉堆代码分享

2021-02-02 11:43zhangqi66 Java教程

这篇文章主要介绍了java编程实现优先队列的二叉堆代码分享,具有一定参考价值,需要的朋友可以了解下。

这里主要介绍的是优先队列二叉堆Java实现,代码如下:

java" id="highlighter_609460">
?
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
package practice;
import edu.princeton.cs.algs4.StdRandom;
public class TestMain {
  public static void main(String[] args) {
    int[] a = new int[20];
    for (int i = 0; i < a.length; i++) {
      int temp = (int)(StdRandom.random()*100);
      a[i] = temp;
    }
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
    PQHeap pq = new PQHeap();
    for (int i = 0; i < 20; i++) {
      pq.insert(a[i]);
    }
    System.out.println();
    for (int i = 0; i < 20; i++) {
      System.out.print(pq.delMax()+" ");
    }
  }
}
/*
 * 优先队列的堆实现
 * 二叉堆,每个元素有两个子元素,两个子元素均比自己小
 */
class PQHeap{
  private int[] a;
  private int p = 1;
  public PQHeap() {
    a = new int[2];
  }
  /*
   * 插入元素
   */
  public void insert(int elements) {
    if (p == a.length) { resize(a.length*2); }
    a[p++] = elements;
    swim(p - 1); //将刚插入的元素上浮到正确位置
  }
  /*
   * 返回并删除最大元素
   */
  public int delMax() {
    if (p == a.length/4) { resize(a.length/2); }
    int result = a[1]; //找出最大元素
    exch(1, --p); //将最后一个元素移到顶端
    a[p] = 0;
    sink(1); //将刚移上去的元素沉下去,使堆有序
    return result;
  }
  public boolean isEmpty() {
    return p == 0;
  }
  public int size() {
    return p;
  }
  public void show() {
    for (int i : a) {
      System.out.print(i+" ");
    }
    System.out.println();
  }
  /*
   * 上浮元素
   */
  private void swim(int k) { //将元素与父元素比较,比父元素大则换位置
    while (k > 1 && a[k/2] < a[k]) {
      exch(k/2, k);
      k = k/2;
    }
  }
  private void sink(int k) { //将元素与子元素比较,比子元素小则和两个中较大的那个换位置
    while (2*k < p && (a[k] < a[2*k + 1]) || (a[k] < a[2*k])) {
      if (a[2*k + 1] > a[2*k]) { exch(k, 2*k + 1); k = 2*k + 1; }
      else           { exch(k, 2*k); k = 2*k; }
    }
  }
  private void resize(int length) {
    int[] b = new int[length]; //将数组长度改变
    for (int i = 0; i < p; i++) { //将数组复制
      b[i] = a[i];
    }
    a = b; //让a指向b的内存空间
  }
  /*
   * 交换
   */
  private void exch (int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

总结

以上就是本文关于java编程实现优先队列的二叉堆代码分享的全部内容,希望对大家有所帮助。有什么问题可以随时留言,小编会及时回复大家的。感谢朋友们对本站的支持!

原文链接:http://www.cnblogs.com/zhangqi66/p/7245557.html

延伸 · 阅读

精彩推荐