Skip to content

Commit 576a875

Browse files
author
Hubo
committed
top n question
1 parent 0ac036d commit 576a875

2 files changed

Lines changed: 154 additions & 118 deletions

File tree

‎src/data_structure/heap/MinHeap.java‎

Lines changed: 145 additions & 118 deletions
Original file line numberDiff line numberDiff line change
@@ -10,169 +10,196 @@
1010
*/
1111
public class MinHeap<E> {
1212

13-
private Object[] elements;
13+
private Object[] elements;
1414

15-
private int size;
15+
private int size;
1616

17-
private final Comparator<? super E> comparator;
17+
private final Comparator<? super E> comparator;
1818

19-
private static final int DEFAULT_INITIAL_CAPACITY = 11;
19+
private static final int DEFAULT_INITIAL_CAPACITY = 11;
2020

21-
public MinHeap(int initialCapacity, Comparator<? super E> comparator) {
22-
this.elements = new Object[initialCapacity];
23-
this.comparator = comparator;
24-
}
21+
public MinHeap(int initialCapacity, Comparator<? super E> comparator) {
22+
this.elements = new Object[initialCapacity];
23+
this.comparator = comparator;
24+
}
2525

26-
public MinHeap(int initialCapacity) {
27-
this(initialCapacity, null);
28-
}
26+
public MinHeap(int initialCapacity) {
27+
this(initialCapacity, null);
28+
}
2929

30-
public MinHeap(Comparator<? super E> comparator) {
31-
this(DEFAULT_INITIAL_CAPACITY, comparator);
32-
}
30+
public MinHeap(Comparator<? super E> comparator) {
31+
this(DEFAULT_INITIAL_CAPACITY, comparator);
32+
}
3333

34-
public MinHeap() {
35-
this(DEFAULT_INITIAL_CAPACITY, null);
36-
}
34+
public MinHeap() {
35+
this(DEFAULT_INITIAL_CAPACITY, null);
36+
}
3737

38-
// heapify
39-
@SuppressWarnings("unchecked")
40-
public MinHeap(E[] arr) {
41-
int l = arr.length;
38+
// heapify
39+
@SuppressWarnings("unchecked")
40+
public MinHeap(E[] arr) {
41+
int len = arr.length;
4242

43-
this.elements = new Object[l];
44-
this.size = l;
45-
this.comparator = null;
43+
this.elements = new Object[len];
44+
this.size = len;
45+
this.comparator = null;
4646

47-
System.arraycopy(arr, 0, this.elements, 0, l);
47+
System.arraycopy(arr, 0, this.elements, 0, len);
4848

49-
// 从最后一个非叶子节点开始，向前依次对数组中的元素进行自顶向下的堆化操作
50-
// 时间复杂度: O(n)
51-
int nonLeaf = (size - 1) / 2;
52-
for (int i = nonLeaf; i >= 0; i--) {
53-
E element = (E) elements[i];
54-
siftDown(i, element);
55-
}
49+
// 从最后一个非叶子节点开始，向前依次对数组中的元素进行自顶向下的堆化操作
50+
// 时间复杂度: O(n)
51+
int nonLeaf = (size - 1) / 2;
52+
for (int i = nonLeaf; i >= 0; i--) {
53+
E element = (E) elements[i];
54+
siftDown(i, element);
5655
}
57-
58-
private void grow() {
59-
final Object[] newElementData = new Object[elements.length * 2];
60-
System.arraycopy(elements, 0, newElementData, 0, elements.length);
61-
elements = newElementData;
56+
}
57+
58+
private void grow() {
59+
final Object[] newElementData = new Object[elements.length * 2];
60+
System.arraycopy(elements, 0, newElementData, 0, elements.length);
61+
elements = newElementData;
62+
}
63+
64+
@SuppressWarnings("unchecked")
65+
private int compare(E a, E b) {
66+
if (comparator != null) {
67+
return comparator.compare(a, b);
68+
} else {
69+
return ((Comparable<? super E>) a).compareTo(b);
6270
}
63-
64-
@SuppressWarnings("unchecked")
65-
private int compare(E a, E b) {
66-
if (comparator != null) {
67-
return comparator.compare(a, b);
68-
} else {
69-
return ((Comparable<? super E>) a).compareTo(b);
70-
}
71+
}
72+
73+
/**
74+
* 向堆中添加元素
75+
*
76+
* @param element 待添加元素
77+
*/
78+
public void add(E element) {
79+
// assert element is not null
80+
if (elements.length == size) { // 存储小顶堆数据项的数组已满
81+
grow();
7182
}
7283

73-
/**
74-
* 向堆中添加元素
75-
*
76-
* @param element 待添加元素
77-
*/
78-
public void add(E element) {
79-
// assert element is not null
80-
if (elements.length == size) { // 存储小顶堆数据项的数组已满
81-
grow();
82-
}
83-
84-
elements[++size] = element;
84+
elements[++size] = element;
8585

86-
// 自底向上进行堆化操作
87-
int index = size - 1;
88-
if (index != 0) {
89-
siftUp(index, element);
90-
}
86+
// 自底向上进行堆化操作
87+
int index = size - 1;
88+
if (index != 0) {
89+
siftUp(index, element);
9190
}
92-
93-
/**
94-
* 自底向上的堆化操作
95-
*
96-
* @param k 上浮元素在数组中的索引，通常是 this.size - 1
97-
* @param element 待上浮的元素
98-
*/
99-
@SuppressWarnings("unchecked")
100-
private void siftUp(int k, E element) {
101-
91+
}
92+
93+
/**
94+
* 自底向上的堆化操作
95+
*
96+
* @param k 上浮元素在数组中的索引，通常是 this.size - 1
97+
* @param element 待上浮的元素
98+
*/
99+
@SuppressWarnings("unchecked")
100+
private void siftUp(int k, E element) {
101+
102+
/*
102103
while (k > 0) {
103104
int parent = parentIndex(k);
104-
E p = (E) elements[parent];
105+
e p = (e) elements[parent];
105106
106107
if (compare(element, p) >= 0) {
107108
break;
108109
}
109-
elements[k] = parent;
110+
elements[k] = parentl
110111
111112
k = parent;
112113
}
114+
*/
113115

114-
elements[k] = element;
115-
}
116+
for (int parent = parentIndex(k);
117+
k > 0;
118+
k = parent) {
116119

117-
/**
118-
* 取出堆顶元素
119-
*
120-
* @return 堆顶元素
121-
*/
122-
@SuppressWarnings("unchecked")
123-
public E poll() {
124-
if (size == 0) {
125-
return null;
126-
}
127-
final E min = (E) elements[0];
120+
E p = (E) elements[parent];
128121

129-
elements[0] = elements[--size];
130-
elements[size + 1] = null; // let GC do its work
122+
if (compare(element, p) < 0) {
123+
elements[k] = p;
124+
} else {
125+
break;
126+
}
131127

132-
// 自顶向下进行堆化操作
133-
E element = (E) elements[0];
134-
siftDown(0, element);
128+
}
135129

136-
return min;
130+
elements[k] = element;
131+
}
132+
133+
/**
134+
* 取出堆顶元素
135+
*
136+
* @return 堆顶元素
137+
*/
138+
@SuppressWarnings("unchecked")
139+
public E poll() {
140+
if (size == 0) {
141+
return null;
137142
}
143+
final E min = (E) elements[0];
144+
145+
elements[0] = elements[--size];
146+
elements[size + 1] = null; // let GC do its work
138147

139-
/**
140-
* 自顶向下的堆化操作
141-
*
142-
* @param k 待下沉堆顶元素的数组索引，为 0
143-
* @param element 待下沉的堆顶元素
144-
*/
145-
@SuppressWarnings("unchecked")
146-
private void siftDown(int k, E element) {
148+
// 自顶向下进行堆化操作
149+
E element = (E) elements[0];
150+
siftDown(0, element);
147151

148-
int half = size / 2;
149-
while (k < half) {
150-
int child = leftChildIndex(k);
151-
E c = (E) elements[child];
152+
return min;
153+
}
154+
155+
/**
156+
* 自顶向下的堆化操作
157+
*
158+
* @param k 待下沉堆顶元素的数组索引，为 0
159+
* @param element 待下沉的堆顶元素
160+
*/
161+
@SuppressWarnings("unchecked")
162+
private void siftDown(int k, E element) {
163+
164+
int half = size / 2;
165+
while (k < half) {
166+
/*int child = leftChildIndex(k);
167+
E minChild = (E) elements[child];
152168
153169
int right = child + 1;
154-
if (right < size && compare(c, (E) elements[right]) > 0) {
155-
c = (E) elements[child = right];
170+
if (right < size && compare(minChild, (E) elements[right]) > 0) {
171+
minChild = (E) elements[child = right];
156172
}
157173
158-
if (compare(element, c) <= 0) {
174+
if (compare(element, minChild) <= 0) {
159175
break;
160176
}
161-
elements[k] = c;
177+
elements[k] = minChild;
162178
163-
k = child;
164-
}
179+
k = child;*/
165180

166-
elements[k] = element;
167-
}
181+
int left = leftChildIndex(k);
182+
int right = left + 1;
183+
184+
if (right < size) {
185+
E minChild = compare((E) elements[right], (E) elements[left]) < 0
186+
? (E) elements[right]
187+
: (E) elements[left];
188+
}
168189

169-
private int parentIndex(int index) {
170-
return (index - 1) / 2;
171-
}
172190

173-
private int leftChildIndex(int index) {
174-
return 2 * index + 1;
175191
}
176192

193+
elements[k] = element;
194+
}
195+
196+
private int parentIndex(int index) {
197+
return (index - 1) / 2;
198+
}
199+
200+
private int leftChildIndex(int index) {
201+
return 2 * index + 1;
202+
}
203+
177204

178205
}

‎src/data_structure/heap/demo.txt‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
<img src="1.txt"></img>
2+
<img src="1.txt"></img>
3+
<img src="1.txt"></img>
4+
<img src="1.txt"></img>
5+
<img src="1.txt"></img>
6+
<img src="1.txt"></img>
7+
<img src="1.txt"></img>
8+
<img src="1.txt"></img>
9+
<img src="1.txt>

0 commit comments

Comments
 (0)