Java 实现最大堆

最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。

堆接口：

1. /**
2. * Create by zxb on 2017/9/10
3. */
4. public interface IHeap<T extends Comparable<T>> {
6. void display();
8. void initOriginList(List<T> orginList);
10. void makeHeap(int first, int last);
12. void popHeap(int first, int last);
14. void pushHeap(int first, int last);
16. List<T> getHeap();
17. }

堆实现，这里采用的是动态数组来做存储

1. /**
2. * Create by zxb on 2017/9/10
3. */
4. public class HeapImpl<T extends Comparable<T>> implements IHeap<T> {
6. private List<T> heap;
8. private List<T> orginList;
10. public void initOriginList(List<T> orginList) {
11. this.orginList = orginList;
12. }
14. public List<T> getHeap() {
15. return heap;
16. }
18. public HeapImpl() {
19. this.heap = new ArrayList<>();
20. }
22. /**
23. * 插入对应上浮
24. *
25. * @param start
26. */
27. protected void adjustUp(int start) {
28. int currentIndex = start;
29. int parentIndex = (currentIndex - 1) / 2;
30. T tmp = heap.get(currentIndex);
31. while (currentIndex > 0) {
32. int cmp = heap.get(parentIndex).compareTo(tmp);
33. if (cmp >= 0) {
34. break;
35. } else {
36. heap.set(currentIndex, heap.get(parentIndex));
37. currentIndex = parentIndex;
38. parentIndex = (parentIndex - 1) / 2;
39. }
40. }
41. heap.set(currentIndex, tmp);
42. }
44. public void insert(T data) {
45. int size = heap.size();
46. heap.add(data); // 将"数组"插在表尾
47. adjustUp(size); // 向上调整堆
48. }
50. public void remove(int index) {
51. int size = heap.size();
52. heap.set(index, heap.get(size - 1));
53. heap.remove(size - 1);
54. adjustDown(index);
55. }
57. /**
58. * 删除对应下沉
59. *
60. * @param index
61. */
62. private void adjustDown(int index) {
63. int currentIndex = index;
64. int leftChildIndex = index * 2 + 1;
65. int rightChildIndex = index * 2 + 2;
66. T tmp = heap.get(currentIndex);
67. int size = heap.size();
68. while (leftChildIndex < size) {
69. T left = null;
70. T right = null;
71. if (leftChildIndex < size) {
72. left = heap.get(leftChildIndex);
73. }
74. if (rightChildIndex < size) {
75. right = heap.get(rightChildIndex);
76. }
77. int maxIndex = right == null ? leftChildIndex : (left.compareTo(right) >= 0 ? leftChildIndex : rightChildIndex);
78. T max = heap.get(maxIndex);
79. if(tmp.compareTo(max)>=0){
80. break;
81. }else{
82. heap.set(currentIndex, max);
83. heap.set(maxIndex, tmp);
84. leftChildIndex = maxIndex * 2 +1;
85. rightChildIndex = maxIndex +1;
86. }
87. }
88. }
90. public void makeHeap(int first, int last) {
91. for (int i = first; i < last; i++) {
92. insert(orginList.get(i));
93. }
94. }
96. public void popHeap(int first, int last) {
97. remove(first);
98. }
100. public void pushHeap(int first, int last) {
101. adjustUp(last - 1);
102. }
104. public void display() {
105. System.out.println(heap);
106. }
108. public static void main(String[] args) {
109. IHeap<Integer> heap = new HeapImpl<>();
110. heap.initOriginList(Arrays.asList(10, 20, 30, 5, 15));
111. System.out.println("初始构建堆：");
112. heap.makeHeap(0, 5);
113. heap.display();
114. System.out.println("弹出堆顶：");
115. heap.popHeap(0, 5);
116. heap.display();
117. System.out.println("弹出堆顶：");
118. heap.popHeap(0, 4);
119. heap.display();
120. System.out.println("插入堆尾：");
121. heap.getHeap().add(90);
122. heap.display();
123. System.out.println("重新排列：");
124. heap.pushHeap(0, 4);
125. heap.display();
126. }
127. }

运行结果：