堆

1. 什么是堆？

堆是树的一种形式，不同之处在于树上的结点可以随便，堆可以分为大堆和小堆， 大堆：父结点的值一定大于两个子节点。 小堆：父节点的值一定小于两个字结点。

2.堆的内存方式？

数组

3.堆的实现

小堆：

//对任意位置的结点进行调整（向下调整） public static void adjustDown(int[] array, int size, int index) { while (true) { // 1. 判断 index 是不是叶子 int leftIndex = 2 * index + 1; if (leftIndex >= size) { return; } // 2. 找最小的孩子 int minIndex = leftIndex; int rightIndex = leftIndex + 1; if (rightIndex < size && array[rightIndex] < array[leftIndex]) { minIndex = rightIndex; } // 3. 比较最小孩子的值 和 index 位置的值 if (array[index] <= array[minIndex]) { return; } // 4. 交换 int t = array[index]; array[index] = array[minIndex]; array[minIndex] = t; // 5. 把最小的孩子视为 index，继续循环 index = minIndex; } } //建堆 public static void createHeap(int[] array, int size) { //寻找最小的非叶子结点； int leftIndex = (size-1-1)/2; //循环把每个数进行入堆 for(int i = leftIndex;i> = 0;i--) { adjustDown(array,size,i) } } //向上调整(任意位置) public static void adjustUp(int[] array, int size, int index) { //不是父结点一直循环（循环终止条件） while(index != 0) { //找父结点 int indexParent = (index-1)/2; //判断父节点和子节点的大小 if(array[indexParent] > array[index]) { return; } //交换 int temp = array[index]; array[index] = array[indexParent]; array[patent] = temp; //将父结点看作index继续循环 index = indexParent; } }

大堆：

public void up(int[] array,int size,int index) { int leftIndex = index*2 + 1; if(leftIndex > size) { return; } int maxIndex = leftIndex; int rightIndex = leftIndex + 1; if(rightIndex < size && array[rightIndex] > array[leftIndex]) { maxIndex = rightIndex; } if(array[maxIndex] < array[index]) { maxIndex = index; } int temp = array[index]; array[index] = array[maxIndex]; array[maxIndex] = temp; index = maxIndex; } public void setHeap(int[] array,int size) { int index = size - 1; int lastParentIndex = (index-1)/2; for (int i = lastParentIndex;i >= 0 ; i++) { up(array,size,i); } } public void ajustUp(int[] array,int size,int index) { while (index != 0 ) { int indexParent = (index - 1)/2; if(array[indexParent] < array[index]) { break; } int temp = array[index]; array[index] = array[indexParent]; array[indexParent] = temp; index = indexParent; } }

4.java的堆:

//有限队列本质就是小堆 Queue<Integer> priorityQueue = new PriorityQueue<>();

5.利用优先队列实现大堆

Queue<Integer> priorityQueue = new PriorityQueue<>((o1,o2) -> o2-o1);