数据结构与算法之堆
由于之前失误 在堆排序中没有列出堆的实现 现在补上
public class MaxHeap { /** 所谓大顶堆 就是每个树的父节点都比其左右子节点大 */ /** * 堆 */ private int[] heap; /** * 界限 */ private final int limit; /** * 堆中数据个数 */ private int heapSize; /** * 构造器 */ public MaxHeap(int limit) { this.limit = limit; heap = new int[limit]; heapSize = 0; } public static void main(String[] args) { MaxHeap maxHeap = new MaxHeap(10); maxHeap.push(3); maxHeap.push(6); maxHeap.push(5); maxHeap.push(2); maxHeap.push(7); maxHeap.push(0); maxHeap.push(11); maxHeap.push(22); maxHeap.push(4); ArrayUtil.printArray(maxHeap.heap); maxHeap.pop(); } public void push(int value) { if (heapSize == limit) { throw new RuntimeException(" is full"); } heap[heapSize] = value; /** 调节堆 */ heapInsert(heap, heapSize++); } /** 堆弹出 返回最大值并且保证大顶堆数据结构不变 */ public int pop(){ int resultVal = heap[0]; /** 将最后一个叶子节点提到根接单上 */ ArrayUtil.swap(heap,0,--heapSize); heapify(heap,0,heapSize); return resultVal; } public void heapInsert(int[] heap, int index) { /** * arr[index] * arr[index] 不比 arr[index父]大了 , 停 * index = 0; */ while (heap[index] > heap[(index - 1) / 2]) { ArrayUtil.swap(heap, index, (index - 1) / 2); index = (index - 1) / 2; } } public void heapify(int [] heap, int index, int heapSize){ /** * 从index位置,往下看,不断的下沉, * 停:我的孩子都不再比我大;已经没孩子了; * * 左右两个孩子中,谁大,谁把自己的下标给largest * 右 -> 1) 有右孩子 && 2)右孩子的值比左孩子大才行 * 否则,左 */ /** 左节点 */ int left = index * 2 + 1; /** 如果一直有左孩子 */ while(left < heapSize){ /** 左右两个孩子中谁的比较大 那么就返回谁 */ int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left; largest = heap[largest] > heap[index] ? largest : index; if (largest == index) { break; } ArrayUtil.swap(heap,index,largest); index = largest; left = index * 2 +1; } } }