数据结构与算法系列笔记六：堆、优先队列

本文主要是介绍数据结构与算法系列笔记六：堆、优先队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

堆

1 堆的定义

堆：是一类特殊的数据结构的统称，通常可以被看做是一颗完全二叉树的数组对象。

堆的特性

1. 完全二叉树。除了树的最后一层节点不需要是满的，其他每一层从左到右都是满的，如果最后一层节点不是满的，那么要求左满右不满。

2. 数组实现

   

   如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。

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

2 堆的API设计

package study.algorithm.heap;

public class Heap<T extends Comparable<T>> {
  //存储堆中的元素
  private T[] items;
  //记录堆中元素的个数
  private int N;

  public Heap(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }

  public int size() {
    return this.N;
  }

  public T get(int i) {
    return items[i];
  }

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

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

  //往堆中插入元素
  public void insert(T t) {
    items[++N] = t;
    swim(N);
  }

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

  //删除堆中最大的元素，并返回这个最大元素
  public T delMax() {
    T max = items[1];
    //交换索引i处的元素和最大索引处的元素，让完全二叉树中最底层最右侧的元素变为临时根节点
    swap(1, N);
    //删除最大索引处的元素
    items[N] = null;
    //元素个数-1
    N--;
    //通过下沉算法，调整堆，让堆重新有序
    sink(1);
    return max;
  }

  //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
  private void sink(int k) {
    //通过循环不断对比当前k节点和其子节点2k以及2k+1处中较大值的元素大小。如果当前节点小，则交换位置
    while (2 * k <= N) {
      //获取当前节点的子节点中的较大节点
      int max;//记录较大节点所在索引值
      if (items[2 * k + 1] == null) {
        max = 2 * k;
      } else {
        max = less(2 * k, 2 * k + 1) ? 2 * k + 1 : 2 * k;
      }
      //比较当前节点和较大节点的值
      if (less(k, max)) {
        swap(max, k);
        k = max;
        continue;
      } else {
        break;
      }
    }
  }
    
}

3 堆排序

package study.algorithm.heap;

public class HeapSort {

  //数组从小到大排序
  public static void sort(Comparable[] a) {
    //构建堆
    Comparable[] heap = new Comparable[a.length + 1];
    createHeap(a, heap);
    //定义一个变量，记录未排序的元素中最大的索引
    int N = heap.length - 1;
    //通过循环，交换1索引处的元素和未排序的元素中最大的索引处的元素
    while (N != 1) {
      //交换元素
      swap(heap, 1, N);
      //排序交换后最大元素所在的索引，让它不要参与堆的下沉调整
      N--;
      //需要对索引1处的元素进行堆的下沉调整
      sink(heap, 1, N);
    }
    //把heap中的数据复制到原数组中
    System.arraycopy(heap, 1, a, 0, a.length);
  }

  //根据原数组source，构造出堆heap
  private static void createHeap(Comparable[] source, Comparable[] heap) {
    //把source中的元素拷贝到heap中，此时heap中的元素就形成一个无序的堆
    System.arraycopy(source, 0, heap, 1, source.length);
    //对堆中的元素做下沉调整（从长度的一半处开始，往索引处1处扫描）
    for (int i = heap.length / 2; i > 0; i--) {
      sink(heap, i, heap.length - 1);
    }
  }

  //在 heap 堆中，对 target 处的元素做下沉，范围是 0-range
  private static void sink(Comparable[] heap, int target, int range) {
    while (2 * target <= range) {
      int max;
      if (2 * target == range) {
        max = 2 * target;
      } else {
        max = less(heap[2 * target], heap[2 * target + 1]) ? 2 * target + 1 : 2 * target;
      }
      if (less(heap[target], heap[max])) {
        swap(heap, target, max);
        target = max;
      } else {
        break;
      }
    }
  }

  private static boolean less(Comparable a, Comparable b) {
    return a.compareTo(b) < 0;
  }

  private static void swap(Comparable[] heap, int i, int j) {
    Comparable temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
  }
}

堆排序算法分析

• 下沉算法复杂度为O(logn)，堆排序的时间复杂度O(NlogN)，额外空间复杂度O(1)，是一个不稳定的排序算法

优先队列

优先队列按照其作用不同，可以分为一下两种：

最大优先队列：

• 可以获取并删除队列中最大的值

最小优先队列：

• 可以获取并删除队列中最小的值

1 最大优先队列

基于堆实现最大优先队列

API实现与堆实现一模一样

package study.algorithm.priority;

public class MaxPriorityQueue<T extends Comparable<T>> {
  //存储堆中的元素
  private T[] items;
  //记录堆中元素的个数
  private int N;

  public MaxPriorityQueue(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }


  public int size() {
    return this.N;
  }

  public boolean isEmpty() {
    return this.N == 0;
  }

  private boolean less(int i, int j) {
    return items[i].compareTo(items[j]) < 0;
  }

  private void swap(int i, int j) {
    T temp = items[i];
    items[i] = items[j];
    items[j] = temp;
  }

  public void insert(T t) {
    items[++N] = t;
    swim(N);
  }

  public T delMax() {
    T max = items[1];
    swap(1, N);
    N--;
    sink(1);
    return max;
  }

  //使用上浮算法，使索引k处的元素在堆中处于一个正确的位置
  private void swim(int k) {
    while (k > 1) {
      if (less(k / 2, k)) {
        swap(k / 2, k);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  //使用下沉算法，使索引k处的元素在堆中处于一个正确的位置
  private void sink(int k) {
    while (2 * k <= N) {
      int max;
      if (2 * k == N) {
        max = 2 * k;
      } else {
        max = less(2 * k, 2 * k + 1) ? 2 * k + 1 : 2 * k;
      }
      if (less(k, max)) {
        swap(k, max);
        k = max;
      } else {
        break;
      }
    }
  }

}

2 最小优先队列

最小优先队列同样是基于堆实现的，满足两个特性：

1. 最小的元素放在数组的索引1处
2. 每个节点的数据总是小于等于它的两个子节点的数据

package study.algorithm.priority;

public class MinPriorityQueue<T extends Comparable<T>> {
  //存储堆中的元素
  private T[] items;
  //记录堆中元素的个数
  private int N;

  public MinPriorityQueue(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.N = 0;
  }

  public int size() {
    return this.N;
  }

  public boolean isEmpty() {
    return this.N == 0;
  }

  private boolean less(int i, int j) {
    return items[i].compareTo(items[j]) < 0;
  }

  private void swap(int i, int j) {
    T temp = items[i];
    items[i] = items[j];
    items[j] = temp;
  }

  public void insert(T t) {
    items[++N] = t;
    swim(N);
  }

  public T delMin() {
    T min = items[1];
    swap(1, N);
    N--;
    sink(1);
    return min;
  }

  //使用上浮算法，使索引k处的元素在堆中处于一个正确的位置
  private void swim(int k) {
    while (k > 1) {
      if (less(k, k / 2)) {
        swap(k / 2, k);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  //使用下沉算法，使索引k处的元素在堆中处于一个正确的位置
  private void sink(int k) {
    while (2 * k <= N) {
      int min;
      if (2 * k == N) {
        min = 2 * k;
      } else {
        min = less(2 * k, 2 * k + 1) ? 2 * k : 2 * k + 1;
      }
      if (less(min, k)) {
        swap(k, min);
        k = min;
      } else {
        break;
      }
    }
  }

}

3 索引优先队列

在之前实现的最大优先队列和最小优先队列，他们可以分别快速访问到队列中最大元素和最小元素，但是他们有一个缺点，就是没有办法**通过索引访问已存在于优先队列中的对象，并更新它们。**为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列。接下来我们以最小索引优先队列举列。

索引优先队列实现思路

步骤1

可以用一个T[] items数组来保存数据元素，在insert(int k,T t)完成插入时，可以把k看做是items数组的索引，把t元素放到items数组的索引k处，这样我们再根据k获取元素t时就很方便了，直接就可以拿到items[k]即可。

步骤2

items数组中的元素顺序是随机的，并不是堆有序的，所以，为了完成这个需求，我们可以增加一个数组int[]pq,来保存每个元素在items数组中的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。

步骤3

我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是pq数组。如果需要对items中的元素进行修改，比如让items[0]=“H”,那么很显然，我们需要对pq中的数据做堆调整，而且是调整pq[9]中元素的位置。但现在就会遇到一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需要挑中pq[9]中元素的位置呢？
最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可，但是效率很低。
我们可以另外增加一个数组，int[] qp,用来存储pq的逆序。

当有了pq数组后，如果我们修改items[0]=“H”，那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0]=9,那么直接调整pq[9]即可。

索引优先队列API实现

package study.algorithm.priority;

public class IndexMinPriorityQueue<T extends Comparable<T>> {
  //用来存储元素的数组
  private T[] items;
  //保存每个元素在items数组中的索引，pq数组堆有序
  private int[] pq;
  //保存pq的逆序，pq的值作为索引，pq的索引作为值
  private int[] qp;
  //记录堆中元素的个数
  private int N;

  public IndexMinPriorityQueue(int capacity) {
    this.items = (T[]) new Comparable[capacity + 1];
    this.pq = new int[capacity + 1];
    this.qp = new int[capacity + 1];
    this.N = 0;

    //默认情况下，队列中没有存储任何数据，让qp中的元素都为-1
    for (int i = 0; i < qp.length; i++) {
      qp[i] = -1;
    }
  }

  public int size() {
    return N;
  }

  public boolean isEmpty() {
    return N == 0;
  }

  public boolean contains(int k) {
    return qp[k] != -1;
  }

  //最小元素关联的索引
  public int minIndex() {
    return pq[1];
  }

  public void insert(int i, T t) {
    //判断i是否被关联。如果已经被关联，则不让插入
    if (contains(i)) {
      return;
    }
    //元素个数+1
    N++;
    //把数据存储到items对应的i位置处
    items[i] = t;
    //把i存储到pq中
    pq[N] = i;
    //通过qp来记录pq中的i
    qp[i] = N;
    //通过上浮算法调整堆
    swim(N);
  }

  public int delMin() {
    //获取最小元素关联的索引
    int minIndex = pq[1];
    //交换pq中索引1处和最大索引处的元素
    swap(1, N);
    //删除pq中对应的内容
    qp[pq[N]] = -1;
    //删除pq中最大索引处的内容
    pq[N] = -1;
    //删除items中对应的内容
    items[minIndex] = null;
    //元素个数-1
    N--;
    //下沉调整
    sink(1);
    return minIndex;
  }

  public void delete(int i) {
    //找到i在pq中的索引
    int k = qp[i];
    //交换pq中索引k处的值和索引N处的值
    swap(k, N);
    //删除qp中的内容
    qp[pq[N]] = -1;
    //删除pq中的内容
    pq[N] = -1;
    //删除items中的内容
    items[k] = null;
    //元素的数量-1
    N--;
    //堆的调整
    sink(k);
    swim(k);
  }

  //修改索引i处的元素为t
  public void changeItem(int i, T t) {
    //修改items数组中i位置的元素为t
    items[i] = t;
    //找到i在pq中出现的位置
    int k = qp[i];
    //堆调整
    sink(k);
    swim(k);
  }

  private void swim(int k) {
    while (k > 1) {
      if (less(k, k / 2)) {
        swap(k, k / 2);
        k = k / 2;
      } else {
        break;
      }
    }
  }

  private void sink(int k) {
    while (2 * k <= N) {
      int min;
      if (2 * k == N) {
        min = 2 * k;
      } else {
        min = less(2 * k, 2 * k + 1) ? 2 * k : 2 * k + 1;
      }
      if (less(k, min)) {
        break;
      }
      swap(k, min);
      k = min;
    }
  }

  private boolean less(int i, int j) {
    return items[pq[i]].compareTo(items[pq[j]]) < 0;
  }

  private void swap(int i, int j) {
    //交换pq中的数据
    int temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;

    //更新qp中的数据
    qp[pq[i]] = i;
    qp[pq[j]] = j;
  }


}

这篇关于数据结构与算法系列笔记六：堆、优先队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！