赞
踩
1)堆结构就是用数组实现的完全二叉树结构
2)完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3)完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4)堆结构的插入和调整操作
5)堆结构的增大和减少
6)优先级队列结构,就是堆结构
堆排序
1.先让整个数组都变成大根堆结构,建立堆的过程
1)从上往下的方法,时间复杂度为O(NlogN)
2) 从下到上的方法,时间复杂度为O(N)
2.把堆的最大值和堆末尾的值交换,然后减少堆的大小之后,再去调整堆,一直周而复始,时间复杂度为O(NlogN)
3.堆的大小减少成0之后,排序完成
堆的如堆和出堆如下:
package class04; public class Code02_Heap01 { public static class MyMaxHeap{ private int[] heap; private int limit; private int heapSize; public MyMaxHeap(int limit){ heap = new int[limit]; this.limit = limit; heapSize = 0; } public boolean isEmpty(){ return heapSize==0; } public boolean isfull(){ return heapSize == limit; } public void pop(int value){ if (heapSize == limit) throw new RuntimeException("heap is full"); heap[heapSize] = value; heapinsert(heap,heapSize++); } private void heapinsert(int[] arr,int index){ while (arr[index] > arr[(index - 1) / 2 ]){ swap(arr,index,(index - 1 )/ 2); index = ( index - 1 ) / 2 ; } } public void swap(int[]arr,int i ,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public int pop(){ int ans = heap[0]; swap(heap,0,--heapSize); heapify(heap,0,heapSize); return ans; } private void heapify(int[] arr,int index,int heapSize){ int left = index * 2 + 1; while (left < heapSize){ int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ?largest : index; if (largest == index) break; swap(arr,index,largest); index = largest; left = index * 2 + 1 ; } } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。