Skip to content

Commit 265e44b

Browse files
SitroneSitrone
committed
大顶堆实现
1 parent f14a598 commit 265e44b

1 file changed

Lines changed: 173 additions & 0 deletions

File tree

‎algorithms/MaxPQ.java‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
package com.algs;
2+
3+
import java.util.Iterator;
4+
5+
import edu.princeton.cs.algs4.StdIn;
6+
import edu.princeton.cs.algs4.StdOut;
7+
8+
/*
9+
* 优先队列基于二叉堆实现，数据存储在数组pq[1 ... N]中，其中pq[0]不使用
10+
*/
11+
public class MaxPQ<Key extends Comparable<Key>> implements Iterable<Key>
12+
{
13+
private static final int DEFAULT_LENGTH = 1 << 4;
14+
15+
private Key[] pq;
16+
private int N = 0;
17+
18+
public MaxPQ()
19+
{
20+
this(DEFAULT_LENGTH);
21+
}
22+
23+
@SuppressWarnings("unchecked")
24+
public MaxPQ(int capacity)
25+
{
26+
pq = (Key[]) new Comparable[capacity + 1];
27+
}
28+
29+
@SuppressWarnings("unchecked")
30+
public MaxPQ(Key[] keys)
31+
{
32+
int N = keys.length;
33+
pq = (Key[]) new Comparable[N + 1];
34+
for(int i = 0; i < N; i++) pq[i + 1] = keys[i];
35+
for(int k = N/2; k > 1; k--) swin(k); // 堆有序
36+
37+
assert isMaxPQ();
38+
}
39+
40+
public boolean isEmpty()
41+
{
42+
return N == 0;
43+
}
44+
45+
public int size()
46+
{
47+
return N;
48+
}
49+
50+
public void insert(Key v)
51+
{
52+
if(N == pq.length - 1) resize(N + N / 2);
53+
pq[++N] = v;
54+
swin(N);
55+
56+
assert isMaxPQ();
57+
}
58+
59+
public Key delMax()
60+
{
61+
Key max = pq[1];
62+
exch(1, N--);
63+
pq[N + 1] = null; // 防止对象游离
64+
if(N > 0 && N == pq.length / 4) resize(pq.length / 2);
65+
sink(1);
66+
67+
assert isMaxPQ();
68+
return max;
69+
}
70+
71+
private boolean less(int i, int j)
72+
{
73+
return pq[i].compareTo(pq[j]) < 0;
74+
}
75+
76+
private void exch(int i, int j)
77+
{
78+
Key t = pq[i];
79+
pq[i] = pq[j];
80+
pq[j] = t;
81+
}
82+
83+
private void swin(int k)
84+
{
85+
while (k > 1 && less(k / 2, k))
86+
{
87+
exch(k / 2, k);
88+
k = k / 2;
89+
}
90+
}
91+
92+
private void sink(int k)
93+
{
94+
while (2 * k <= N)
95+
{
96+
int j = 2 * k;
97+
if (j < N && less(j, j + 1)) j++; // 找到两个子节点中较大的
98+
if (!less(k, j)) break; // 若父节点大于较大的子节点，则两者交换
99+
exch(k, j);
100+
k = j;
101+
}
102+
}
103+
104+
private void resize(int capacity)
105+
{
106+
assert capacity > N;
107+
@SuppressWarnings("unchecked")
108+
Key[] temp = (Key[]) new Comparable[capacity + 1];
109+
System.arraycopy(getClass(), 0, temp, 0, N);
110+
pq = temp;
111+
}
112+
113+
private boolean isMaxPQ()
114+
{
115+
return isMaxPQ(1);
116+
}
117+
118+
private boolean isMaxPQ(int k)
119+
{
120+
if(k > N) return true;
121+
int left = 2 * k, right = 2 * k + 1;
122+
123+
if(left < N && less(k, left)) return false;
124+
if(left < N && less(k, right)) return false;
125+
126+
return isMaxPQ(left) && isMaxPQ(right);
127+
}
128+
129+
@Override
130+
public Iterator<Key> iterator()
131+
{
132+
return new HeapIterator();
133+
}
134+
135+
public class HeapIterator implements Iterator<Key>
136+
{
137+
private MaxPQ<Key> clone;
138+
139+
public HeapIterator()
140+
{
141+
clone = new MaxPQ<>(size());
142+
for(int i = 1; i < size(); i++) clone.insert(pq[i]);
143+
}
144+
@Override
145+
public boolean hasNext()
146+
{
147+
return !clone.isEmpty();
148+
}
149+
150+
@Override
151+
public Key next()
152+
{
153+
if(!hasNext()) throw new UnsupportedOperationException(); ;
154+
return clone.delMax();
155+
}
156+
157+
public void remove()
158+
{
159+
throw new UnsupportedOperationException();
160+
}
161+
}
162+
163+
public static void main(String[] args)
164+
{
165+
MaxPQ<String> pq = new MaxPQ<String>();
166+
while (!StdIn.isEmpty()) {
167+
String item = StdIn.readString();
168+
if (!item.equals("-")) pq.insert(item);
169+
else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
170+
}
171+
StdOut.println("(" + pq.size() + " left on pq)");
172+
}
173+
}

0 commit comments

Comments
 (0)