FilesExpand file tree

master

/

MinPQ.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

174 lines (144 loc) · 3.45 KB

master

/

MinPQ.java

Copy path

Top

File metadata and controls

• Code
• Blame

174 lines (144 loc) · 3.45 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

package com.algs;

import java.util.Iterator;

import edu.princeton.cs.algs4.StdIn;

import edu.princeton.cs.algs4.StdOut;

public class MinPQ<Key extends Comparable<Key>>

{

private Key[] pq;

private int N;

public MinPQ()

{

this(1 << 4);

}

@SuppressWarnings("unchecked")

public MinPQ(int capacity)

{

pq = (Key[]) new Comparable[capacity];

N = 0;

}

public MinPQ(Key[] keys)

{

}

public boolean isEmpty()

{

return N == 0;

}

public int size()

{

return N;

}

public void insert(Key key)

{

if(N > 0 && N == pq.length) resize(2 * pq.length);

pq[++N] = key;

swin(N);

assert isMinPQ();

}

public Key min()

{

return pq[1];

}

public Key delMin()

{

Key min = pq[1];

exch(1, N--);

pq[N + 1] = null;

if(N > 0 && N == pq.length / 4) resize(pq.length / 2);

sink(1);

assert isMinPQ();

return min;

}

public void sink(int k)

{

while(2 * k < N)

{

int j = 2 * k;

if(j < N && less(j + 1, j)) j++;

if(less(k, j)) break;

exch(k, j);

k = j;

}

}

public void swin(int k)

{

while(k > 1 && less(k, k/2))

{

exch(k/2, k);

k = k/2;

}

}

public boolean isMinPQ()

{

return isMinPQ(1);

}

public boolean isMinPQ(int k)

{

if(k > N) return true;

int left = 2 * k, right = 2 * k + 1;

if(left > N && less(left, k)) return false;

if(left > N && less(right, k)) return false;

return isMinPQ(left) && isMinPQ(right);

}

private void resize(int capacity)

{

assert capacity > N;

@SuppressWarnings("unchecked")

Key[] temp = (Key[]) new Comparable[capacity + 1];

System.arraycopy(pq, 0, temp, 0, N);

pq = temp;

}

private boolean less(int i, int j)

{

return pq[i].compareTo(pq[j]) < 0;

}

private void exch(int i, int j)

{

Key t = pq[i];

pq[i] = pq[j];

pq[j] = t;

}

public Iterator<Key> iterator()

{

return new HeapIterator();

}

public class HeapIterator implements Iterator<Key>

{

private MinPQ<Key> clone;

public HeapIterator()

{

clone = new MinPQ<>(size());

for(int i = 1; i < size(); i++) clone.insert(pq[i]);

}

@Override

public boolean hasNext()

{

return !clone.isEmpty();

}

@Override

public Key next()

{

if(!hasNext()) throw new UnsupportedOperationException(); ;

return clone.delMin();

}

public void remove()

{

throw new UnsupportedOperationException();

}

}

/**

* A test client.

*/

public static void main(String[] args) {

MinPQ<String> pq = new MinPQ<String>();

while (!StdIn.isEmpty()) {

String item = StdIn.readString();

if (!item.equals("-")){

pq.insert(item);

}

else if (!pq.isEmpty()){

StdOut.print(pq.delMin() + " ");

}

}

StdOut.println("(" + pq.size() + " left on pq)");

}

}