FilesExpand file tree

 master

/

MergeSortedArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

157 lines (125 loc) · 4.27 KB

 master

/

MergeSortedArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

157 lines (125 loc) · 4.27 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

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Queue;

import java.util.LinkedList;

/**

* merge K sorted arrays into one. total: N

* min heap: O(NlgK)

*/

public class MergeSortedArray {

private static class ArrayNode {

public Integer value;

public int arrayIndex;

public ArrayNode(Integer v, int index) {

value = v;

arrayIndex = index;

}

public String toString() {

return String.valueOf(value);

}

} // end of ArrayNode

private static class MinHeapArrayNode {

private ArrayList<ArrayNode> heap;

public MinHeapArrayNode() {

heap = new ArrayList<ArrayNode>();

// 1 is the min one.

// it is easy to calculate left, right and parent

heap.add(null);

}

public void insert(ArrayNode node) {

if(node == null)

throw new RuntimeException("can't insert null node");

heap.add(node);

shiftUp(heap.size() - 1);

}

public ArrayNode removeMin() {

if (isEmpty())

throw new RuntimeException("heap is empty");

// System.out.println(heap.toString());

ArrayNode min = heap.get(1);

heap.remove(min);

if (heap.size() != 1) {

shiftDown(1);

}

return min;

}

private void shiftUp(int k) {

//k/2 parent

while (k > 1 && greater(k / 2, k)) {

swap(k / 2, k);

k = k / 2;

}

}

private void shiftDown(int k) {

while (2 * k <= heap.size() - 1) {

int i = 2 * k; //left

int j = i + 1; //right

//find the smallest of left and right

if (i < heap.size() - 1 && greater(i, j)) {

i++; // i = j;

}

if (greater(i, k)) break;

swap(i, k);

k = i;

}

}

private boolean greater(int i, int j) {

if (i > 0 && j < heap.size()) {

return heap.get(i).value > heap.get(j).value;

}

return false;

}

private void swap(int i, int j) {

ArrayNode tmp = heap.get(i);

heap.set(i, heap.get(j));

heap.set(j, tmp);

}

private boolean isEmpty() {

return heap.size() == 1;

}

} // end of MinHeapArrayNode

public static void main(String[] args) {

Integer[][] arrays = new Integer[][]{

{1, 5, 9},

{4, 8, 10,13},

{6, 11},

{2,7}

};

ArrayList<Integer> result = mergeSortedArray(arrays);

System.out.println(result.toString());

}

public static ArrayList<Integer> mergeSortedArray(Integer[][] arrays) {

ArrayList<Integer> result = new ArrayList<Integer>();

ArrayList<Queue<Integer>> lists = new ArrayList<Queue<Integer>>();

for (int i = 0; i < arrays.length; i++) {

ArrayList<Integer> tmpArray = new ArrayList<Integer>(Arrays.asList(arrays[i]));

Queue<Integer> tmpQueue = new LinkedList<Integer>(tmpArray);

lists.add(tmpQueue);

}

MinHeapArrayNode heap = new MinHeapArrayNode();

// initialize minheap

for (int i = 0; i < lists.size(); i++) {

heap.insert(new ArrayNode(lists.get(i).poll(), i));

}

boolean done = false;

while (!done) {

ArrayNode minNode = heap.removeMin();

result.add(minNode.value);

int nextIndex = minNode.arrayIndex;

Queue<Integer> nextQueue = lists.get(nextIndex);

while (nextQueue.size() == 0) {

nextIndex = (nextIndex < lists.size() - 1) ? nextIndex + 1 : 0;

nextQueue = lists.get(nextIndex);

if (nextIndex == minNode.arrayIndex) {

done = true;

break;

}

}

if (!done)

heap.insert(new ArrayNode(nextQueue.poll(), nextIndex));

}

while (!heap.isEmpty())

result.add(heap.removeMin().value);

return result;

}

}