Skip to content

Commit 1512c5b

Browse files
author
chenpiqian
committed
00
1 parent ffdf299 commit 1512c5b

3 files changed

Lines changed: 505 additions & 0 deletions

File tree

‎note/src/main/java/com/datastructure/_6_MaxHeap.java‎

Lines changed: 246 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,257 @@
11
package com.datastructure;
22

3+
import java.util.Random;
4+
35
/**
46
* @Description
57
* @Author chenpiqian
68
* @Date: 2019-08-08
79
*/
810
public class _6_MaxHeap {
911

12+
static public class Array<E> {
13+
14+
private E[] data;
15+
private int size;
16+
17+
// 构造函数，传入数组的容量capacity构造Array
18+
public Array(int capacity){
19+
data = (E[])new Object[capacity];
20+
size = 0;
21+
}
22+
23+
// 无参数的构造函数，默认数组的容量capacity=10
24+
public Array(){
25+
this(10);
26+
}
27+
28+
// 获取数组中的元素个数
29+
public int getSize(){
30+
return size;
31+
}
32+
33+
// 返回数组是否为空
34+
public boolean isEmpty(){
35+
return size == 0;
36+
}
37+
38+
// 在index索引的位置插入一个新元素e
39+
public void add(int index, E e){
40+
41+
if(index < 0 || index > size)
42+
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
43+
44+
if(size == data.length)
45+
resize(2 * data.length);
46+
47+
for(int i = size - 1; i >= index ; i --)
48+
data[i + 1] = data[i];
49+
50+
data[index] = e;
51+
52+
size ++;
53+
}
54+
55+
// 向所有元素后添加一个新元素
56+
public void addLast(E e){
57+
add(size, e);
58+
}
59+
60+
// 获取index索引位置的元素
61+
public E get(int index){
62+
if(index < 0 || index >= size)
63+
throw new IllegalArgumentException("Get failed. Index is illegal.");
64+
return data[index];
65+
}
66+
67+
// 修改index索引位置的元素为e
68+
public void set(int index, E e){
69+
if(index < 0 || index >= size)
70+
throw new IllegalArgumentException("Set failed. Index is illegal.");
71+
data[index] = e;
72+
}
73+
74+
// 从数组中删除index位置的元素, 返回删除的元素
75+
public E remove(int index){
76+
if(index < 0 || index >= size)
77+
throw new IllegalArgumentException("Remove failed. Index is illegal.");
78+
79+
E ret = data[index];
80+
for(int i = index + 1 ; i < size ; i ++)
81+
data[i - 1] = data[i];
82+
size --;
83+
data[size] = null; // loitering objects != memory leak
84+
85+
if(size == data.length / 4 && data.length / 2 != 0)
86+
resize(data.length / 2);
87+
return ret;
88+
}
89+
90+
91+
// 从数组中删除最后一个元素, 返回删除的元素
92+
public E removeLast(){
93+
return remove(size - 1);
94+
}
95+
96+
97+
public void swap(int i, int j){
98+
99+
if(i < 0 || i >= size || j < 0 || j >= size)
100+
throw new IllegalArgumentException("Index is illegal.");
101+
102+
E t = data[i];
103+
data[i] = data[j];
104+
data[j] = t;
105+
}
106+
107+
@Override
108+
public String toString(){
109+
110+
StringBuilder res = new StringBuilder();
111+
res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
112+
res.append('[');
113+
for(int i = 0 ; i < size ; i ++){
114+
res.append(data[i]);
115+
if(i != size - 1)
116+
res.append(", ");
117+
}
118+
res.append(']');
119+
return res.toString();
120+
}
121+
122+
// 将数组空间的容量变成newCapacity大小
123+
private void resize(int newCapacity){
124+
125+
E[] newData = (E[])new Object[newCapacity];
126+
for(int i = 0 ; i < size ; i ++)
127+
newData[i] = data[i];
128+
data = newData;
129+
}
130+
}
131+
132+
133+
134+
135+
static public class MaxHeap<E extends Comparable<E>>{
136+
137+
private Array<E> data;
138+
139+
public MaxHeap(int capacity){
140+
data = new Array<>(capacity);
141+
}
142+
143+
public MaxHeap(){
144+
data = new Array<>();
145+
}
146+
147+
// 返回堆中的元素个数
148+
public int size(){
149+
return data.getSize();
150+
}
151+
152+
// 返回一个布尔值, 表示堆中是否为空
153+
public boolean isEmpty(){
154+
return data.isEmpty();
155+
}
156+
157+
// 父亲节点下标
158+
private int parent(int index){
159+
if(index == 0)
160+
throw new IllegalArgumentException("index-0 doesn't have parent.");
161+
return (index - 1) / 2;
162+
}
163+
164+
// 左孩子下标
165+
private int leftChild(int index){
166+
return index * 2 + 1;
167+
}
168+
169+
// 右孩子下标
170+
private int rightChild(int index){
171+
return index * 2 + 2;
172+
}
173+
174+
// 添加元素
175+
public void add(E e){
176+
// 在数组末尾添加元素
177+
data.addLast(e);
178+
// 数组末尾元素和父节点元素比较，可能会互换位置
179+
siftUp(data.getSize() - 1);
180+
}
181+
182+
// 数组末尾元素和父节点元素比较，可能会互换位置
183+
private void siftUp(int k){
184+
// 父亲元素比当前元素大
185+
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
186+
// 当前元素和父亲元素互换位置
187+
data.swap(k, parent(k));
188+
// 设置下标k为parent(k)，继续循环直到退出循环
189+
k = parent(k);
190+
}
191+
}
192+
193+
public E findMax(){
194+
if (data.getSize() == 0)
195+
throw new RuntimeException("没元素了");
196+
return data.get(0);
197+
}
198+
199+
private void siftDown(int k){
200+
while (leftChild(k) < data.getSize()){
201+
// 获取左孩子下标
202+
int j = leftChild(k);
203+
// j+1即为右孩子下标，比较左右孩子的大小
204+
if (j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0)
205+
// 若右孩子大，则将j设置为右孩子下标
206+
j++;
207+
208+
// 当前元素大于最大的左右孩子，退出循环
209+
if (data.get(k).compareTo(data.get(j)) >= 0)
210+
break;
211+
212+
// 当前元素和最大的左右孩子互换下标
213+
data.swap(k, j);
214+
// 元素换到了下标j的位置，所以k要设置为j
215+
k = j;
216+
}
217+
}
218+
219+
public E extractMax(){
220+
E ret = findMax(); // 查找最大值
221+
data.swap(0, data.getSize() -1); // 数组头尾元素互换
222+
data.removeLast(); // 删除数组最后一个元素
223+
siftDown(0); // 从下标为0的元素与左右孩子比较，换位置
224+
return ret;
225+
}
226+
227+
}
228+
229+
230+
231+
232+
233+
234+
public static void main(String[] args) {
235+
236+
int n = 10000;
237+
238+
MaxHeap<Integer> maxHeap = new MaxHeap<>();
239+
Random random = new Random();
240+
for(int i = 0 ; i < n ; i ++)
241+
maxHeap.add(random.nextInt(10000));
242+
243+
int[] arr = new int[n];
244+
for(int i = 0 ; i < n ; i ++){
245+
arr[i] = maxHeap.extractMax();
246+
System.out.println(arr[i]);
247+
}
248+
249+
for(int i = 1 ; i < n ; i ++)
250+
if(arr[i-1] < arr[i])
251+
throw new IllegalArgumentException("Error");
252+
253+
System.out.println("Test MaxHeap completed.");
254+
}
255+
10256

11257
}

0 commit comments

Comments
 (0)