
本文共 6862 字,大约阅读时间需要 22 分钟。
������������������������������
������������������������������������������������������������������������������������������������������������������������������������������������������������������
���������������������������������������������������������������������������������������������������������������Priority Queue������������������������������������Min-Heap������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
������������������������������
������������������������������������������������������������������
��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������� size
��������������������������������������������� capacity
��������������������������������������������� 100
���
���������������������������������������������������������������������������������������������������������
arr
���������������������������������size
������������������������������������������
���������������shiftDown���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
���������������shiftUp���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������
���������������������
������������������������������������������������������
1. ���������������shiftDown���
��������� shiftDown
���������������������������������������������������������������������
public void shiftDown(int[] arr, int index, int size) { int parent = index; int child = 2 * parent + 1; while (child < size) { // ��������������������������������� if (child + 1 < size && arr[child] > arr[child + 1]) { child = child + 1; } // ������������������������������������ if (arr[child] < arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; } else { break; } parent = child; child = 2 * parent + 1; }}
��������������������������������������� index
���������������������������������������������������������������������������������������������������������������
2. ���������������shiftUp���
shiftUp
������������������������������������������������������������������������������������������������������������������
public void shiftUp(int[] arr, int size, int index) { int child = index; int parent = (child - 1) / 2; while (child > 0) { // ������������������������������������ if (arr[child] < arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; } else { break; } child = parent; parent = (child - 1) / 2; }}
������������������������������������������ shiftUp
���������������������������������������������������������������������������������������������������������������������������������������
������������
���������������������������������������������������������������������������������������������
public class MyPriorityQueue { private int[] arr = new int[100]; private int size = 0; @Override public String toString() { int[] copy = Arrays.copyOf(arr, size); return Arrays.toString(copy); } public void shiftDown(int[] arr, int index, int size) { int parent = index; int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && arr[child] > arr[child + 1]) { child = child + 1; } if (arr[child] < arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; } else { break; } parent = child; child = 2 * parent + 1; } } public void shiftUp(int[] arr, int size, int index) { int child = index; int parent = (child - 1) / 2; while (child > 0) { if (arr[child] < arr[parent]) { int tmp = arr[child]; arr[child] = arr[parent]; arr[parent] = tmp; } else { break; } child = parent; parent = (child - 1) / 2; } } public void creatHeap(int[] newArr) { for (int x : newArr) { arr[size++] = x; } for (int i = (size - 1 - 1) / 2; i >= 0; i--) { shiftDown(arr, i, size); } } public void creatHeap2(int[] arr) { for (int x : arr) { offer(x); } } public void offer(int val) { if (size >= arr.length) { return; } arr[size++] = val; shiftUp(arr, size, size - 1); } public Integer peek() { if (size == 0) { return null; } return arr[0]; } public Integer poll() { if (size == 0) { return null; } int res = arr[0]; int temp = arr[0]; arr[0] = arr[size - 1]; arr[size - 1] = temp; size--; shiftDown(arr, 0, size); return res; }}
������������
������������������������������������������������������������������������������
public static void main(String[] args) { MyPriorityQueue m = new MyPriorityQueue(); m.offer(6); m.offer(5); m.offer(4); m.offer(3); int[] arr = {9, 2, 7}; m.creatHeap(arr); System.out.println(m.peek()); // ���������������������3 Integer res = m.poll(); System.out.println(res); // ���������������������3 res = m.poll(); System.out.println(res); // ���������������������4}
���������������������������������������������������������������������������������������������������������������
334
������
���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������heap��������������������������������������������������������������������������������������������������� Ensureheap property���
���������������������������������������������������������������������������������������������������������������������������������������������������
发表评论
最新留言
关于作者
