堆排序 | flybread

堆排序算法描述+代码实现

在处理大数据的时候有时候会用到这个堆的数据结构。

网上对于解决海量前K大问题比较常用的方法就是堆排。我们知道，使用堆排序是要求堆可以放入内存啊，这么大的数据，怎么放？这里有一个技巧，内存中并不是放入所有数据的堆，而是放入K大小的堆，我们知道堆调整的复杂度为lgK，使用K大小的堆，文件遍历一遍我们就可以求出前K大，所以复杂度是NlgK，N是词的个数，只不过这个“遍历”是文件操作，系数要比在内存中“遍历”的系数要大一些。

/**
 * @author zhailz
 * 堆排序，不稳定的算法，最好的情况O(nlogn),最坏的情况O(nlogn),平均的情况是O(nlogn)
 */
public class HeapSort {

  public static void main(String[] args) {
    int[] arrays = new int[] { 5, 1, 6, 2, 4, 10, 16, 0 };
    hearpSort(arrays);
    System.out.println(Arrays.toString(arrays));
  }

  public static int[] hearpSort(int[] arrays) {
    creatheap(arrays);
    System.out.println(Arrays.toString(arrays));
    for (int i = arrays.length - 1; i > 0; i--) {
      swap(arrays, 0, i);
      mainHeap(arrays, 0, i);
    }
    return arrays;
  }

  public static int[] creatheap(int[] arrays) {
    for (int i = arrays.length / 2; i >= 0; i--) {
      mainHeap(arrays, i, arrays.length);
    }
    return arrays;
  }

  private static void mainHeap(int[] arrays, int i, int length) {
    //
    int largest = i;
    if (left(i) < length && arrays[left(i)] > arrays[largest]) {
      largest = left(i);
    }

    if (right(i) < length && arrays[right(i)] > arrays[largest]) {
      largest = right(i);
    }

    if (largest != i) {
      swap(arrays, i, largest);
      mainHeap(arrays, largest, length);
    }
  }

  private static void swap(int[] arrays, int i, int largest) {
    int temp = arrays[i];
    arrays[i] = arrays[largest];
    arrays[largest] = temp;
  }

  private static int left(int i) {
    return 2 * i + 1;
  }

  private static int right(int i) {
    return 2 * i + 2;
  }
}