每日一学——堆

特点 (1)堆是一种特殊的完全二叉树； (2)通过数组的方式顺序存储； (3)对于任意节点来说，满足根节点大于左右子树的值（大堆）或者满足根节点的值小于左右子树的值（小堆）作用：用来高效找出最值元素 典型问题：TopK问题向上调整与向下调整 (1)向下调整:是让调整的结点与其孩子节点进行比较 (2)向上调整:是让调整的结点与其父亲结点进行比较 若已知根节点的位置为index，则左子树的位置为2index+1; 右子树位置为2index+2; 若已知左子树的位置为leftIndex,则父节点的位置为(leftIndex-1)÷2； public class TestHeap { //index 表示要调整的位置 //size表示数组的长度 public void adjustDown(int[] array,int size,int index){ while (true) { //leftChild表示最后一个叶子节点 int leftChild = index * 2 + 1; //判断index的叶子节点是否存在，不存在直接return if (leftChild >= size) { return; } //假设当前的叶子节点位置处的值最小 int minIndex = leftChild; int rightChild = leftChild + 1; //判断右子树节点是否存在，并且判断右子树的值是否小于左子树的值 if (rightChild < size && array[rightChild] < array[leftChild]) { minIndex = rightChild; } //判断minIndex处的值和index处的值得大小，如果index位置的值更小，则break;否则交换两处的值 if (array[index] <= array[minIndex]) { break; } int tmp = array[index]; array[index] = array[minIndex]; array[minIndex] = tmp; //将minIndex赋值给index继续循环 index = minIndex; } } public void createHeap(int[] array,int size){ //lastIndex表示最后一个叶子节点 int lastIndex = size-1; //lastParentIndex表示最后一个叶子节点的父节点 int lastParentIndex = (size-1-1)/2; for (int i = lastParentIndex; i >= 0 ; i--) { adjustDown(array,size,i); } } } public class TestHeapP { public void adjustUp(int[] array,int size,int index){ while(true){ //判断当前节点是不是根节点，如果是根节点，直接退出 if (index == 0){ break; } //找到父节点 int parentIndex = (index-1)/2; //如果父节点的值本来就小于index位置的值，那么直接break,邹泽交换父节点和index位置的值 if (array[parentIndex] < array[index]){ break; } int tmp = array[parentIndex]; array[parentIndex] = array[index]; array[index] = tmp; //将当前parentIndex赋值给index继续循环 index = parentIndex; } } public void createHeap(int[] array,int size){ //lastIndex表示最后一个叶子节点 int lastIndex = size-1; //lastParentIndex表示最后一个叶子节点的父节点 int lastParentIndex = (size-1-1)/2; for (int i = lastParentIndex; i >= 0 ; i--) { adjustUp(array,size,i); } } } 优先队列的实现 public class MyPriorityQueue { public int[] array = new int[100]; public int size = 0; public void adjustUp(int[] array,int size,int index){ while(true){ if (index == 0){ break; } int parentIndex = (index-1)/2; if (array[parentIndex] < array[index]){ break; } int tmp = array[parentIndex]; array[parentIndex] = array[index]; array[index] = tmp; index = parentIndex; } } public void offer(int x){ array[size] = x; size++; adjustUp(array,array.length,size-1); } public void adjustDown(int[] array,int size,int index){ while (true){ int leftChild = index*2+1; if (leftChild >= size){ return; } int minIndex = leftChild; int rightChild = leftChild+1; if (rightChild < size && array[rightChild] < array[minIndex]){ minIndex = rightChild; } if (array[index] < array[minIndex]){ break; } int tmp = array[minIndex]; array[minIndex] = array[index]; array[index] = tmp; index = minIndex; } } public Integer poll(){ if (size == 0){ return null; } int ret = array[0]; array[0] = array[size-1]; size--; adjustDown(array,size,0); return ret; } public Integer peek(){ if (size == 0){ return null; } return array[0]; } public boolean isEmpty(){ return size == 0; } }