思维导图：
1.优先级队列：
- 队列的特点是先进先出，优先级队列中则是优先级高的元素先出队列。
- 堆是将所有元素按完全二叉树的顺序存储方式存储到一个数组中，如果根节点的值大于孩子节点则称大根堆；若根节点的值小于孩子节点则称为小根堆；堆总是一颗完全二叉树。
- 完全二叉树可以采用层序遍历的规则按照顺序存储到数组中，而非完全二叉树则不适合，容易造成空间的浪费空间利用率低下。
- 堆的创建，在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整，建堆的时间复杂度为O(n)。//建立大根堆，每一棵子树的调整属于向下调整
public void createHeap(){ for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) { shiftDown(parent,usedSize); } } //向下调整 public void shiftDown(int parent,int len){ int child = parent*2 + 1; //parent和child只是下标 while(parent < len){ if(child+1 < len && elem[child] < elem[child+1]){ child++; } if(elem[child] > elem[parent]){ int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = 2*parent + 1
- 堆的插入涉及到了向上调整，插入和删除元素的时间复杂度都为O(log2N)。//入堆，需要向上调整
public void offer(int x){ if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } this.elem[usedSize] = x; usedSize++; shiftUp(usedSize-1); } private boolean isFull() { return usedSize == elem.length; } //向上调整 public void shiftUp(int child){ int parent = (child-1)/2; while(child > 0){ if(elem[child] > elem[parent]){ int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child-1)/2; }else{ break; } } }
- 优先级队列的删除操作，删除的是堆顶的元素，将要删除的堆顶元素和最后元素交换，然后让usedSize--，再让0下标向下调整即可；插入和删除元素的时间复杂度为O(log2N)。//出堆，需要向下调整
public int poll(){ if(isEmpty()){ return -1; } int oldvalue = elem[0]; int tmp = elem[0]; elem[0] = elem[usedSize-1]; elem[usedSize-1] = tmp; usedSize--; shiftDown(0,usedSize); return oldvalue; } private boolean isEmpty(){ return usedSize == 0; }
- 优先级队列模拟实现时，就是将完全二叉树使用数组的形式存储起来
1. class TestHeap{ 2. public int[] elem; 3. public int usedSize; 4. 5. public TestHeap() { 6. this.elem = new int[10]; 7. this.usedSize = usedSize; 8. } 9. 10. public void initArray(int[] array){ 11. elem = Arrays.copyOf(array,array.length*2); 12. usedSize = elem.length; 13. } 14. //建立大根堆 15. public void createHeap(){ 16. for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) { 17. shiftDown(parent,usedSize); 18. } 19. } 20. //向下调整 21. public void shiftDown(int parent,int len){ 22. int child = parent*2 + 1; 23. 24. while(parent < len){ 25. if(child+1 < len && elem[child] < elem[child+1]){ 26. child++; 27. } 28. if(elem[child] > elem[parent]){ 29. int tmp = elem[child]; 30. elem[child] = elem[parent]; 31. elem[parent] = tmp; 32. parent = child; 33. child = 2*parent + 1; 34. } 35. else{ 36. break; 37. } 38. } 39. } 40. 41. //入堆，需要向上调整 42. public void offer(int x){ 43. if(isFull()){ 44. elem = Arrays.copyOf(elem,elem.length*2); 45. } 46. this.elem[usedSize] = x; 47. usedSize++; 48. shiftUp(usedSize-1); 49. 50. 51. } 52. 53. private boolean isFull() { 54. return usedSize == elem.length; 55. } 56. 57. //向上调整 58. public void shiftUp(int child){ 59. int parent = (child-1)/2; 60. while(child > 0){ 61. if(elem[child] > elem[parent]){ 62. int tmp = elem[child]; 63. elem[child] = elem[parent]; 64. elem[parent] = tmp; 65. child = parent; 66. parent = (child-1)/2; 67. }else{ 68. break; 69. } 70. } 71. } 72. 73. //出堆，需要向下调整 74. public int poll(){ 75. if(isEmpty()){ 76. return -1; 77. } 78. int oldvalue = elem[0]; 79. int tmp = elem[0]; 80. elem[0] = elem[usedSize-1]; 81. elem[usedSize-1] = tmp; 82. usedSize--; 83. shiftDown(0,usedSize); 84. return oldvalue; 85. } 86. private boolean isEmpty(){ 87. return usedSize == 0; 88. } 89. } 90. 91. public class Main { 92. public static void main(String[] args) { 93. int[] elem = { 27,15,19,18,28,34,65,49,25,37 }; 94. TestHeap testHeap = new TestHeap(); 95. testHeap.initArray(elem); 96. testHeap.createHeap(); 97. System.out.println("调试！"); 98. } 99. }
2.PriorityQueue特性：
- PriorityQueue底层是使用堆来实现的，默认情况为小堆。如果需要大根堆需要提供比较器。
- 优先级队列底层数组默认大小是11；没有容量限制，可以插入多个元素。如果容量小于64数组会按照2倍扩容。容量大于等于64数组会按照1.5倍扩容。
- PriorityQueue放的元素必须可以比较，不可以插入不能比较的元素和null，比较器需要自己传入如果不传入默认这个数据是可以比较的，默认实现Comparable接口的。//方法1
class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { //小根堆 return o1 - o2; //大根堆 return o2 - o1; } } public static void main(String[] args) { PriorityQueue priorityQueue = new PriorityQueue<>(new IntCmp()); } //方法2 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { //大根堆 return o2 - o1; } });
3.优先级队列的使用：
- topK问题，时间复杂度为O(N log2N)
top-K问题：
1.求前k个最大的，建大小为k的小堆。拿剩下的元素和堆顶元素比较，剩下元素大于堆顶，则删除堆顶元素，入大的元素。
2.求前k个最小的，建大小为k的大堆。拿剩下的元素和堆顶元素比较，剩下元素小于堆顶，则删除堆顶元素，入小的元素。
3.求第k个最大的，建大小为k的小堆，堆顶元素就是第k个最大的。拿剩下的元素和堆顶元素比较，剩下元素大于堆顶，则删除堆顶元素，入大的元素。
4.求第k个最小的，建大小为k的大堆，堆顶元素就是第k个最小的。拿剩下的元素和堆顶元素比较，剩下元素小于堆顶，则删除堆顶元素，入小的元素。
- 堆排序，若将一组数据从小到大排序，要求在原数组上进行调整，不得创建新的数组。解题思路：建立大根堆；将堆顶元素也就是最大值和最后一个下标元素交换；交换后向下调整再让end--即可。此处留心shiftDown(array, 0, end); 后再 end--;
top-k问题的代码实现：
1. public int[] smallestK(int[] array,int k){ 2. int[] ret = new int[k]; 3. if(k == 0) return ret; 4. 5. PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() { 6. @Override 7. public int compare(Integer o1, Integer o2) { 8. return o2 - o1; 9. } 10. }); 11. for (int i = 0; i < array.length; i++) { 12. if(priorityQueue.size() < k){ 13. priorityQueue.offer(array[i]); 14. }else{ 15. int top = priorityQueue.peek(); 16. if(array[i] < top){ 17. priorityQueue.poll(); 18. priorityQueue.offer(array[i]); 19. } 20. } 21. } 22. for (int i = 0; i < k; i++) { 23. ret[i] = priorityQueue.poll(); 24. } 25. return ret; 26. }
堆排序的代码实现：
1. //堆排序 2. public void shiftDown(int parent,int len){ 3. int child = 2*parent + 1; 4. 5. while(child <len ){ 6. if(child+1 < len && elem[child] < elem[child+1]){ 7. child++; 8. } 9. if(elem[child] > elem[parent]){ 10. int tmp = elem[child]; 11. elem[child] = elem[parent]; 12. elem[parent] = tmp; 13. parent = child; 14. child = 2*parent + 1; 15. }else{ 16. break; 17. } 18. } 19. } 20. //建立一个大根堆 21. public void createHeap(){ 22. for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) { 23. shiftDown(parent,usedSize); 24. } 25. } 26. //实现堆排序 27. public void heapSort() { 28. 29. int end = usedSize - 1; 30. while (end > 0) { 31. swap(array, 0, end); 32. shiftDown(array, 0, end); 33. end--; 34. } 35. }
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
