python堆排序求topn_堆排序和topN算法
堆排序和topN算法:
topN算法，第一次調(diào)用topN，然后把海量數(shù)據(jù)一次和小頂堆第一個比較，如果>第一個元素，就交換，然后調(diào)用minHeapify方法排序一遍。
然后比較下一個數(shù)據(jù)。
public class HeapSortAndTopN {
public static void main(String[] args) {
int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
new HeapSortAndTopN().sort(arr);
System.out.println(Arrays.toString(arr));
}
public void sort(int[] a) {
int len = a.length;
int firstNonLeafIndex = (len - 2)/2;
for(int i = firstNonLeafIndex; i >=0 ; i --) {
maxHeapify(a,len,i);
}
for(int j = len - 1; j > 0 ; j --) {
swap(a,j,0);
maxHeapify(a,j,0);
}
}
private void maxHeapify(int[] a, int len, int subTreeNodeMax) {
int left = subTreeNodeMax * 2 + 1;
int right = subTreeNodeMax * 2 + 2;
int maxIndex = subTreeNodeMax;
if(left < len && a[left] > a[maxIndex]) {
maxIndex = left;
}
if(right < len && a[right] > a[maxIndex]) {
maxIndex = right;
}
if(maxIndex != subTreeNodeMax) {
swap(a, maxIndex, subTreeNodeMax);
maxHeapify(a, len, maxIndex);
}
}
private void minHeapify(int[] a, int len, int subTreeNodeMax) {
int left = subTreeNodeMax * 2 + 1;
int right = subTreeNodeMax * 2 + 2;
int maxIndex = subTreeNodeMax;
if(left < len && a[left] < a[maxIndex]) {
maxIndex = left;
}
if(right < len && a[right] < a[maxIndex]) {
maxIndex = right;
}
if(maxIndex != subTreeNodeMax) {
swap(a, maxIndex, subTreeNodeMax);
maxHeapify(a, len, maxIndex);
}
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
public int[] topN(int[] array) {
if(array != null && array.length > 0) {
int arrayLen = array.length;
int firtNonLeafIndex = (arrayLen - 2) / 2;
for(int i = firtNonLeafIndex; i >= 0 ; i --) {
minHeapify(array, arrayLen, i);
}
}
return array;
}
}
總結(jié)
以上是生活随笔為你收集整理的python堆排序求topn_堆排序和topN算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 华为ap配置_Win10频发蓝屏，深度D
- 下一篇： trunc 文字与格式与字符串不符_EX