堆的定义

堆是计算机科学中一类特殊的数据结构的统称,堆通常可以被看做是一棵完全二叉树的数组对象

堆的特性

  1. 它是完全二叉树,除了树的最后一层节点不需要是满的,其它的每一层从左到右都是满的,如果最后一层节点不是满的,那么要求左满右不满
  2. 它通常用数组来实现,具体的方法就是将二叉树的节点按照层级顺序放入到数组中,根节点在位置1,它的子节点在位置$2$和$3$,而子节点的子节点则分别在位置$4,5,6$和$7$,以此类推

如果一个节点的位置为$k$,则它的父节点的位置为$\frac{k}{2}$,而它的两个子节点的位置则分别为$2k$和$2k+1$,这样在不使用指针的情况下,我们也可以通过计算数组的索引在树中上下移动:想要$a$节点$k$向上移动一层,就令$k=\frac{k}{2}$,向下一层就令$k=2k$或$k=2k+1$

  1. 每个节点都大于等于它的两个子节点,这里需要注意堆中仅仅规定了每个节点大于等于它的两个子节点,但这两个子节点的顺序并没有做规定,这跟我们之前所学习的二叉查找树是有区别的

堆的API设计

类名Heap>
构造方法Heap(int capacity):创建容量为capacity的Heap对象
成员方法1.private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素 2.private void exch(int i,int j):交换堆中i索引和j索引处的值 3.public T delMax():删除堆中最大的元素,并返回这个最大元素 4.public void insert(T t):往堆中插入一个元素 5.private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置 6.private void sink(int k):使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
成员变量1.private T[] imtes:用来存储元素的数组 2.private int N:记录堆中元素的个数

堆的实现

insert插入方法的实现

堆是用数组完成数据元素的存储,由于数组的底层是一串连续的内存地址,所以我们要往堆中插入数据,我们只能往数组中从索引$0$处开始,依次往后存放数据,但是堆中对元素的顺序是有要求的,每一个节点的数据要大于等于它的两个子节点的数据,所以每次插入一个元素,都会使得堆中的数据顺序变乱,这个时候我们就需要通过一些方法让刚才插入的这个数据放入到合适的位置

所以如果往堆中插入新的元素,我们只需要不断的比较新节点$a[k]$和它的父节点$a[\frac{k}{2}]$的大小,然后根据结果完成数据元素的交换,就可以完成堆的有序调整

delMax删除最大元素方法的实现

由堆的特性我们可以知道,索引$1$处的元素,也就是根节点就是最大的元素,当我们把根节点的元素删除后,需要有一个新的根节点出现,这时候我们可以暂时把堆中最后一个元素放到索引$1$处,充当根节点,但是它有可能不满足堆的序性需求,这个时候我们就需要通过一些方法,让这个新的根节点放入到合适的位置

所以,当删除掉最大元素后,只需要将最后一个元素放到索引$1$处,并不断的拿着当前节点$a[k]$与它的子节点$a[2k]$和$a[2k+1]$中较大者交换位置,即可以完成堆的有序调整

代码实现

Heap

public class Heap<T extends Comparable<T>> {

  /**
   * 存储堆中的元素
   */
  private T[] items;
  /**
   * 记录堆中元素的个数
   */
  private int N;

  /**
   * 创建容量为capacity的Heap对象
   */
  public Heap(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }

  /**
   * 判断堆中索引i处的元素是否小于索引j处的元素
   */
  private boolean less(int i, int j) {
    return items[i].compareTo(items[j]) < 0;
  }

  /**
   * 交换堆中i索引和j索引处的值
   */
  private void exch(int i, int j) {
    T temp = items[i];
    items[i] = items[j];
    items[j] = temp;
  }

  /**
   * 删除堆中最大的元素,并返回这个最大元素
   */
  public T delMax() {
    T max = items[1];
    //交换索引1处的元素和最大索引处的元素(也就是数组最后个元素),让完全二叉树中最右侧的元素变为临时根节点
    exch(1, N);
    //删除掉最大索引处的元素
    items[N] = null;
    //元素个数-1
    N--;
    //使用下沉算法调整,让堆重新有序
    sink(1);
    return max;
  }

  /**
   * 往堆中插入一个元素
   */
  public void insert(T t) {
    //因为堆是从数组第1个位置开始的,所以是++N,成功跳过0位置
    items[++N] = t;
    //又因为是从数组尾部插入,如果遇到插入的元素比他的父节点更大,就需要使用上浮算法,从下到上进行寻找正确的位置
    swim(N);
  }

  /**
   * 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void swim(int k) {
//通过循环,不断的比较当前节点的值和其父节点的值,如果其父节点小于当前节点,则交换位置
    while (k > 1) {
      //比较当前节点与它父节点,交换元素
      if (less(k / 2, k)) {
        exch(k / 2, k);
        //再变化k值
        k = k / 2;
      } else {
        break;
      }
    }
  }

  /**
   * 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
   */
  private void sink(int k) {
    //通过循环,不断的比较当前节点的值与其两个节点(左子节点与右子节点)的值,与其中大的子节点进行交换位置
    while (2 * k <= N) {
      //获取当前节点的子节点中的较大节点
      //记录较大节点所在的索引
      int max;
      //如果有右子节点
      if (2 * k + 1 <= N) {
        //如果左子节点小于右子节点,则max为右子节点
        if (less(2 * k, 2 * k + 1)) {
          max = 2 * k + 1;
        }//相反则max为左子节点
        else {
          max = 2 * k;
        }
      }//若果没有右子节点,则只有一个左子节点,直接令max=左子节点即可
      else {
        max = 2 * k;
      }
      //比较当前节点与较大子节点的值
      //如果当前节点的值比子节点的值小,则交换
      if (less(k, max)) {
        exch(k, max);
      }//大于则不用继续循环了,直接break
      else {
        break;
      }
      //最后还要更新变换k的值
      k = max;
    }
  }
}

HeapTest

public static void main(String[] args) {
    //创建堆对象
    Heap<String> stringHeap = new Heap<>(10);
    //往堆中存入字符串数据
    stringHeap.insert("A");
    stringHeap.insert("B");
    stringHeap.insert("C");
    stringHeap.insert("D");
    stringHeap.insert("E");
    stringHeap.insert("F");
    stringHeap.insert("G");
    //通过循环从堆中删除数据
    String result = null;
    while ((result = stringHeap.delMax()) != null) {
      System.out.print(result + " ");
    }
  }

堆排序

给定一个数组

String[] arr={"S","O","R","T","E","X","A","M","P","L","E"}

请对数组中的字符按照从小到大进行排序

API设计
类名HeapSort>
成员方法1.public static void sort(Comparable[] source):对source数组中的数据从小到大进行排序 2.private static void createHeap(Comparable[] source,Comparable[] heap):根据原数组source,构造出堆heap 3.private static boolean less(Comparable[] heap,int i,int j):判断heap堆中索引i处的元素是否小于索引j处的元素 4.private static void exch(Comparable[] heap,int i,int j):交换heap堆中i索引和j索引处的值 5.private static void sink(Comparable[] heap,int target,int range):在heap堆中,对target处的元素做下沉,范围是0~range
实现步骤
  1. 构造堆
  2. 得到堆顶元素,这个值就是最大值
  3. 交换堆顶元素和数组中的最后一个元素,此时所有元素中的最大元素已经放到合适的位置
  4. 对堆进行调整,重新让除了最后一个元素的剩余元素中的最大值放到堆顶
  5. 重复2~4这个步骤,直到堆中剩一个元素为止

堆构造过程

堆的构造,最直观的想法就是另外再创建一个新数组,然后从左往右遍历原数组,每得到一个元素后,添加到新数组中,并通过上浮,对堆进行调整,最后新的数组就是一个堆

上述的方式虽然很直观,也很简单,但是我们可以用更聪明一点的方法来实现它,创建一个新数组,把原数组0~length-1的数据拷贝到新数组的1~length处,再从新数组长度的一半处开始往1索引处扫描(从右往左),然后对扫描到的每一个元素做下沉调整即可

堆排序过程

对构造好的堆,我们只需要做类似于堆的删除操作,就可以完成排序

  1. 将堆顶元素和堆中最后一个元素交换位置
  2. 通过对堆顶元素下沉调整,把最大的元素放到堆顶(此时最后一个元素不参与堆的调整,因为最大的数据已经到了数组的最右边)
  3. 重复1~2步骤,直到堆中剩下最后一个元素

代码实现

HeapSort

public class HeapSort {

  /**
   * 判断heap堆中索引i处的元素是否小于索引j处的元素
   */
  private static boolean less(Comparable[] heap, int i, int j) {
    return heap[i].compareTo(heap[j]) < 0;
  }

  /**
   * 交换heap堆中i索引和j索引处的值
   */
  private static void exch(Comparable[] heap, int i, int j) {
    Comparable tmp = heap[i];
    heap[i] = heap[j];
    heap[j] = tmp;
  }

  /**
   * 根据原数组source,构造出堆heap
   */
  private static void createHeap(Comparable[] source, Comparable[] heap) {
    //把source数组中的元素拷贝到heap数组中,此时的heap数组是个无序的堆,需要对其进行排序
    System.arraycopy(source, 0, heap, 1, source.length);
    //使用下沉调整,范围为(1~length/2),因为使用下沉排序,所以是要寻找2k的子节点,所以为了节省时间,从中间length/2开始找
    for (int i = (heap.length) / 2; i > 0; i--) {
      //从i开始,到堆的末尾结束,进行下沉
      sink(heap, i, heap.length - 1);
    }
  }

  /**
   * 对source数组中的数据从小到大进行排序
   */
  public static void sort(Comparable[] source) {
    //构建堆
    //之所以长度+1,那是因为原数组是0开始,堆是1开始,这时候的Heap就是无序的数组
    Comparable[] heap = new Comparable[source.length + 1];
    createHeap(source, heap);
    //定义一个变量,记录未排序的元素中最大的索引,初始值从最后开始,所以长度-1
    int N = heap.length - 1;
    //通过循环,交换1索引处和数组元素中最大索引处的元素
    while (N > 1) {
      //交换元素
      exch(heap, 1, N);
      //将两个索引的值进行交换,然后将最大索引排开,让它不要参与下沉
      N--;
      //从1索引开始进行下沉
      sink(heap, 1, N);
    }
    //把Heap中的数据复制到原数组source中
    System.arraycopy(heap, 1, source, 0, source.length);
  }

  /**
   * 在heap堆中,对target处的元素做下沉运算,范围是0~range
   */
  private static void sink(Comparable[] heap, int target, int range) {
    while (2 * target <= range) {
      //找出当前节点的较大的子节点
      int max;
      if (2 * target + 1 <= range) {
        if (less(heap, target * 2, target * 2 + 1)) {
          max = target * 2 + 1;
        } else {
          max = target * 2;
        }
      } else {
        max = target * 2;
      }
      //比较当前节点的值与较大子节点的值
      if (less(heap, target, max)) {
        exch(heap, target, max);
        target = max;
      } else {
        break;
      }
    }
  }
}

HeapSortTest

public static void main(String[] args) {
    //待排序数组
    String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
    //通过HeapSort对数组中的元素进行排序
    HeapSort.sort(arr);
    //输入排序后的数组元素
    System.out.println(Arrays.toString(arr));
  }
Last modification:June 16th, 2021 at 11:16 pm