堆和堆排序

作者: TomGui | 来源:发表于2020-06-07 10:38 被阅读0次

    堆定义

    • 堆是一个完全二叉树;
    • 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

    对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作“小顶堆”。

    如何实现一个堆?

    堆都支持哪些操作以及如何存储一个堆。

    用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。

    数组存储堆例子

    从图中我们可以看到,数组中下标为i的节点的左子节点,就是下标为 i2 的节点,右子节点就是下标为 i2+1 的节点,父节点就是下标为 i/2 的节点。

    1. 往堆中插入一个元素

    往堆中插入一个元素后,我们需要继续满足堆的两个特性。于是,我们就需要进行调整,让其重新满足堆的特性,这个过程我们起了一个名字,就叫作堆化(heapify)。

    堆化实际上有两种,从下往上和从上往下。这里我先讲从下往上的堆化方法。

    从下往上堆化
    public class Heap {
      private int[] a; // 数组,从下标 1 开始存储数据
      private int n;  // 堆可以存储的最大数据个数
      private int count; // 堆中已经存储的数据个数
    
      public Heap(int capacity) {
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
      }
    
      public void insert(int data) {
        if (count >= n) return; // 堆满了
        ++count;
        a[count] = data;
        int i = count;
        while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
          swap(a, i, i/2); // swap() 函数作用:交换下标为 i 和 i/2 的两个元素
          i = i/2;
        }
      }
     }
    

    2. 删除堆顶元素

    删除堆顶元素不满足完全二叉树 删除堆顶元素满足完全二叉树
    public void removeMax() {
      if (count == 0) return -1; // 堆中没有数据
      a[1] = a[count];
      --count;
      heapify(a, count, 1);
    }
    
    private void heapify(int[] a, int n, int i) { // 自上往下堆化
      while (true) {
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }
    
    
    private static void buildHeap(int[] a, int n) {
      for (int i = n/2; i >= 1; --i) {
        heapify(a, n, i);
      }
    }
    
    private static void heapify(int[] a, int n, int i) { // 自下往上堆化
      while (true) {
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }
    

    如何基于堆实现排序?

    1. 建堆

    private static void buildHeap(int[] a, int n) {
      for (int i = n/2; i >= 1; --i) {
        heapify(a, n, i);
      }
    }
    
    private static void heapify(int[] a, int n, int i) {
      while (true) {
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }
    

    2. 排序

    // n 表示数据的个数,数组 a 中的数据从下标 1 到 n 的位置。
    public static void sort(int[] a, int n) {
      buildHeap(a, n);
      int k = n;
      while (k > 1) {
        swap(a, 1, k);
        --k;
        heapify(a, k, 1);
      }
    }
    

    相关文章

      网友评论

        本文标题:堆和堆排序

        本文链接:https://www.haomeiwen.com/subject/kgcozhtx.html