• +86-156-1535-0639
  • jianpengqi@126.com

最大根堆java实现

  • QI-Jianpeng

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import java.io.Serializable;
import java.util.Arrays;
/**
* Created by qijianpeng on 16/09/2017.
* mail: jianpengqi@126.com
* 最大根堆实现
*/
public class MaxHeap<E extends Comparable> implements PriorityQueue<E>, Serializable {
private static final long serialVersionUID = 1L;
private Object[] elements = null;
private int size = 0;
private int maxCapacity = 10;
private boolean extendable = true;
public MaxHeap(int maxCapacity, boolean extendable){
this.elements = new Object[maxCapacity + 1];//为了操作方便, 第0个元素不存数据
this.maxCapacity = maxCapacity ;
this.extendable = extendable;
}
public MaxHeap(int maxCapacity){
this.elements = new Object[maxCapacity + 1];//为了操作方便, 第0个元素不存数据
this.maxCapacity = maxCapacity;
}
public MaxHeap(){}
E element(int i){
return (E)elements[i];
}
@Override
public void insert(E e) {
if (size >= maxCapacity && !extendable){
//达到最大容量且不可扩展, 删除堆顶元素
/*elements[size] = e;
rise(size);*/
elements[1] = e;
sink(1);
return;
}else if (size >= maxCapacity && extendable){
//达到最大容量, 但是可扩展, 扩展堆容量
maxCapacity = maxCapacity + (maxCapacity >> 1);
elements = Arrays.copyOf(elements, maxCapacity + 1);
}
elements[++size] = e;
rise(size);
}
@Override
public E top() {
if (size > 0)return element(1);
return null;
}
@Override
public E delTop() {
if (isEmpty())return null;
E top = top();
swap(1, size);//与最后一个节点交换
elements[size] = null;
size--;
if (size > 1) sink(1);
return top;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
/**
* 返回 array[i] < array[j]
* @param i
* @param j
* @return
*/
private boolean less(int i, int j){
return element(i).compareTo(element(j)) < 0;
}
private void swap(int i, int j){
E tmp = element(i);
elements[i] = elements[j];
elements[j] = tmp;
}
/**
* 第{@code k}个元素上浮
* @param k
*/
private void rise(int k){
while (k > 1 && less(k/2, k)){
swap(k/2, k);
k = k/2;
}
}
/**
* 下沉第k个元素
* @param k
*/
private void sink(int k){
while (2 * k <= size){
int j = 2 *k;
if (j < size && less(j, j+ 1))j ++;//第j + 1个元素比第j个元素大
if (!less(k, j))break;//当前节点已经比子节点大
swap(k, j);
k = j;
}
}
public String toString(){
StringBuilder sb = new StringBuilder();
int i;
for (i = 1; i < size; i++){
sb.append(element(i).toString() + ", ");
}
sb.append(element(i).toString());
return sb.toString();
}
public static void main(String[] a){
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(3, false);
maxHeap.insert(3);
maxHeap.insert(5);
maxHeap.insert(9);
System.out.println(maxHeap.toString() + "\t size: "+ maxHeap.size() + " top:" + maxHeap.top());
maxHeap.insert(19);
System.out.println(maxHeap.toString() + "\t size: "+ maxHeap.size() + " top:" + maxHeap.top());
maxHeap.insert(1);
// maxHeap.delTop();
}
}
interface PriorityQueue<E> {
void insert(E e);
E top();
E delTop();
boolean isEmpty();
int size();
}