首页 > 其他分享 >堆、优先队列

堆、优先队列

时间：2022-11-10 20:23:34浏览次数：37  
标签：优先 索引 队列 元素 private int public

堆

堆的定义

  • 堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象
  • 堆的特性：
    • 1.它是完全二叉树，除了树的最后一层结点不需要是满的，其他的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满
    • 2.它通常用数组来实现
      具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4，5，6和7，以此类推
      如果一个结点的位置为k，则它的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以
      通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2，向下一层就令k等于2k或2k+1
    • 3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，
      跟我们之前学习的二叉树是有区别的

堆的API设计

  • 类名：Heap<T extends Comparable>
  • 构造方法：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[k/2]的大小，然后根据结果完成数据元素的交换，
    就可以完成堆的有序调整

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

  • 由堆的特性我们可以知道，索引1处的元素，也就是根结点就是最大的元素，当我们把根结点的元素删除后，需要有一个新的根结点出现，
    这时我们可以暂时把堆中最后一个元素放到索引1处，充当根结点，但是它有可能不满足堆的有序性需求，这个时候我们就需要通过一些方法
    让这个新的根结点放入到合适的位置
  • 所以，当删除掉最大元素后，只需要将最后一个元素放到索引1处，并不断的拿着当前结点a[k]与它的子结点a[2k]和a[2k+1]中的较大者
    交换位置，即可完成堆的有序调整
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;
    }

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

    private void exch(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);
    }

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

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

    private void sink(int k){
        while (2*k<=N){
            int max;
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    max = 2*k+1;
                }else{
                    max = 2*k;
                }
            }else{
                max = 2*k;
            }
            if (!less(k,max)){
                break;
            }
            exch(k,max);
            k = max;
        }
    }
}
public class HeapTest {
    public static void main(String[] args) {
        Heap<String> heap = new Heap<>(10);
        heap.insert("A");
        heap.insert("B");
        heap.insert("C");
        heap.insert("D");
        heap.insert("E");
        heap.insert("F");
        heap.insert("G");

        String result = null;
        while ((result = heap.delMax())!=null){
            System.out.print(result+" ");
        }
    }
}

堆排序

  • 给定一个数组：String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"}
    请对数组中的字符按从小到大排序
  • API设计：
  • 类名：HeapSort<T extends Comparable>
  • 成员方法：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步骤，直到堆中剩最后一个元素
public class HeapSort {
    private static boolean less(Comparable[] heap,int i,int j){
        return heap[i].compareTo(heap[j])<0;
    }

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

    private static void createHeap(Comparable[] source,Comparable[] heap){
        System.arraycopy(source,0,heap,1,source.length);
        for (int i = (heap.length); i > 0; i--) {
            sink(heap,i,heap.length-1);
        }
    }

    public static void sort(Comparable[] source){
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source,heap);
        int N = heap.length-1;

        while (N!=1){
            exch(heap,1,N);
            N--;
            sink(heap,1,N);
        }
        System.arraycopy(heap,1,source,0,source.length);
    }

    private static void sink(Comparable[] heap,int target,int range){
        while (2*target<=range){
            int max;
            if (2*target+1<=range){
                if (less(heap,2*target,2*target+1)){
                    max = 2*target+1;
                }else{
                    max = 2*target;
                }
            }else{
                max = 2*target;
            }
            if (!less(heap,target,max)){
                break;
            }
            exch(heap,target,max);
            target = max;
        }
    }
}
public class HeatSortTest {
    public static void main(String[] args) {
        String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};
        HeapSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

优先队列

  • 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除，在某些情况下，我们可能需要找出队列中的最大值或
    者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我们需要在这些计算机的任务中找出优先级
    最高的任务先执行，执行完毕后就需要把这个任务从队列中移除，普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，
    比较并找出最大值，效率不是很高，这个时候，我们就可以使用一种特殊的队列来完成这种需求，优先队列
  • 优先队列按照其作用不同，可以分为以下两种：
    • 最大优先队列：可以获取并删除队列中最大的值
    • 最小优先队列：可以获取并删除队列中最小的值

最大优先队列

最大优先队列API设计

  • 类名：MaxPriorityQueue<T extends Comparable>
  • 构造方法：MaxPriorityQueue(int capacity)：创建容量为capacity的MaxPriorityQueue对象
  • 成员方法：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处的元素能在堆中处于一个正确的位置
    7.public int size()：获取队列中元素的个数
    8.public boolean isEmpty()：判断队列是否为空
  • 成员变量：1.private T[] imtes：用来存储元素的数组
    2.private int N：记录堆中元素的个数
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 N;
    }

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

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

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

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

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

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

    private void sink(int k){
        while (2*k<=N){
            int max;
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    max = 2*k+1;
                }else{
                    max = 2*k;
                }
            }else{
                max = 2*k;
            }
            if (!less(k,max)){
                break;
            }
            exch(k,max);
            k = max;
        }
    }
}
public class MaxPriorityQueueTest {
    public static void main(String[] args) {
        MaxPriorityQueue<String> queue = new MaxPriorityQueue<>(10);
        queue.insert("A");
        queue.insert("B");
        queue.insert("C");
        queue.insert("D");
        queue.insert("E");
        queue.insert("F");
        queue.insert("G");

        while (!queue.isEmpty()){
            String max = queue.delMax();
            System.out.print(max+" ");
        }
    }
}

最小优先队列

  • 我们前面学习堆的时候，堆中存放数据元素的数组要满足都满足如下特性：
    • 1.最大的元素放在数组的索引1处
    • 2.每个结点的数据总是大于等于它的两个子结点的数据

最小优先队列

最小优先队列API设计

  • 类名：MinPriorityQueue<T extends Comparable>
  • 构造方法：MinPriorityQueue(int capacity)：创建容量为capacity的MinPriorityQueue对象
  • 成员方法：1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素
    2.private void exch(int i,int j)：交换堆中i索引和j索引处的值
    3.public T delMin()：删除队列中最小的元素，并返回这个最小元素
    4.public void insert(T t)：往队列中插入一个元素
    5.private void swim(int k)：使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    6.private void sink(int k)：使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    7.public int size()：获取队列中元素的个数
    8.public boolean isEmpty()：判断队列是否为空
  • 成员变量：1.private T[] imtes：用来存储元素的数组
    2.private int N：记录堆中元素的个数
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 N;
    }

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

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

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

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

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

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

    private void sink(int k){
        while (2*k<=N){
            int min;
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    min = 2*k;
                }else{
                    min = 2*k+1;
                }
            }else{
                min = 2*k;
            }
            if (less(k,min)){
                break;
            }
            exch(k,min);
            k = min;
        }
    }
}
public class MinPriorityQueueTest {
    public static void main(String[] args) {
        MinPriorityQueue<String> queue = new MinPriorityQueue<>(10);
        queue.insert("G");
        queue.insert("F");
        queue.insert("E");
        queue.insert("D");
        queue.insert("C");
        queue.insert("B");
        queue.insert("A");

        while (!queue.isEmpty()){
            String min = queue.delMin();
            System.out.print(min+" ");
        }
    }
}

索引优先队列

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

索引优先队列实现思路

  • 步骤一：
    • 存储数据时，给每一个数据元素关联一个整数，例如insert(int k,T t)，我们可以看做k是t关联的整数，那么我们的
      实现需要通过k这个值，快速获取到队列中t这个元素，此时有个k这个值需要具有唯一性
    • 最直观的想法就是我们可以用一个T[] items数组来保存数据元素，在insert(int k,T t)完成插入时，可以把k看做是
      items数组的索引，把t元素放到items数组的索引k处，这样我们再根据k获取元素t时就很方便了，直接就可以拿到items[k]即可
  • 步骤二：
    • 步骤一完成后的结果，虽然我们给每个元素关联了一个整数，并且可以使用这个整数快速的获得到该元素，但是，items数组中
      的元素顺序是随机的，并不是堆有序的，所以，为了完成这个需求，我们可以增加一个数组int[]pq，来保存每个元素在items数组中
      的索引，pq数组需要堆有序，也就是说，pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]
  • 步骤三：
    • 通过步骤二的分析，我们可以发现，其实我们通过上浮和下沉做堆调整的时候，其实调整的是pq数组。如果需要对items中的元素
      进行修改，比如让items[0]="H"，那么很显然，我们需要对pq中的数据做堆调整，而且是调整pq[9]中元素的位置。但现在就会遇到
      一个问题，我们修改的是items数组中0索引处的值，如何才能快速的知道需要挑中pq[9]中元素的位置呢？
    • 最直观的想法就是遍历pq数组，拿出每一个元素和0做比较，如果当前元素是0，那么调整该索引处的元素即可，但是效率很低，
      我们可以另外增加一个数组，int[]qp，用来存储pq的逆序

索引优先队列API设计

  • 类名：IndexMinPriorityQueue<T extends Comparable>
  • 构造方法：IndexMinPriorityQueue(int capacity)：创建容量为capacity的IndexMinPriorityQueue对象
  • 成员方法：1.private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素
    2.private void exch(int i,int j)：交换堆中i索引和j索引处的值
    3.public T delMin()：删除队列中最小的元素，并返回这个最小元素
    4.public void insert(T t)：往队列中插入一个元素
    5.private void swim(int k)：使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    6.private void sink(int k)：使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    7.public int size()：获取队列中元素的个数
    8.public boolean isEmpty()：判断队列是否为空
    9.public boolean contains(int k)：判断k对应的元素是否存在
    10.public void changeItem(int i,T t)：把与索引i关联的元素修改为t
    11.public int minIndex()：最小元素关联的索引
    12.public void delete(int i)：删除索引i关联的元素
  • 成员变量：1.private T[] imtes：用来存储元素的数组
    2.private int[] pq：保存每个元素在items数组中的索引，pq数组需要堆有序
    3.private int[] qp：保存qp的逆序，pq的值作为索引，pq的索引作为值
    4.private int N：记录堆中元素的个数
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int[] 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;

        for (int i = 0; i < qp.length; i++) {
            qp[i] = -1;
        }
    }

    public int size(){
        return N;
    }

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

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

    private void exch(int i,int j){
        int tmp = pq[i];
        pq[i] = pq[j];
        pq[j] = tmp;

        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

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

    public int minIndex(){

        return pq[1];
    }

    public void insert(int i,T t){
        if (contains(i)){
            return;
        }

        N++;
        items[i] = t;
        pq[N] = i;
        qp[i] = N;

        swim(N);
    }

    public int delMin(){
        int minIndex = pq[1];
        exch(1,N);
        qp[pq[N]] = -1;
        pq[N] = -1;
        items[minIndex] = null;

        N--;
        sink(1);

        return minIndex;
    }

    public void delete(int i){
        int k = qp[i];
        exch(k,N);

        qp[pq[N]] = -1;
        pq[N] = -1;
        items[k]= null;

        N--;
        sink(k);
        swim(k);
    }

    public void changeItem(int i,T t){
        items[i] = t;
        int k = qp[i];
        sink(k);
        swim(k);
    }

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

    private void sink(int k){
        while (2*k<=N){
            int min;
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    min = 2*k;
                }else{
                    min = 2*k+1;
                }
            }else{
                min = 2*k;
            }
            if (less(k,min)){
                break;
            }
            exch(k,min);
            k = min;
        }
    }
}
public class IndexMinPriorityQueueTest {
    public static void main(String[] args) {
        IndexMinPriorityQueue<String> queue = new IndexMinPriorityQueue<>(10);

        queue.insert(0,"A");
        queue.insert(1,"C");
        queue.insert(2,"F");

        queue.changeItem(2,"B");

        while (!queue.isEmpty()){
            int index = queue.delMin();
            System.out.println(index+" ");
        }
    }
}

标签：优先,索引,队列,元素,private,int,public
From： https://www.cnblogs.com/song-hua/p/16873455.html

相关文章

  • Vue中v-if和v-for一起使用时的优先级
     问题：Vue2.0中v-if和v-for一起使用时报错，怎么解决呢？代码和报错信息如下  原因和解决办法：  在处于同一节点的时候，v-for优先级比v-if高。这意味着v-if将分别......
  • 3.两个栈实现一个队列
    两个栈实现一个队列方法一：时间复杂度：push O(1)pop O(n)peek O(n)查看队头元素empty O(1)方法二：pop和peek的时间复杂度为O(n)是因为访问了队头(都位......
  • 广/深度优先搜索与回溯法
    深度优先搜索：在搜索到一个新的节点时，立即对该节点进行遍历；因此需用先入后出的栈，也可以通过与栈等价的递归来实现。深度优先搜索也可以用来检测环路：记录每个遍历过的节点的......
  • 华为&思科设备默认的路由协议优先级
    华为&思科设备默认的路由协议优先级华为设备默认路由协议优先级在华为的设备中，路由器分别定义了外部优先级和内部优先级。外部优先级是指用户可以手工为各路由协议配......
  • 广度优先搜索（BFS）
    基本原理广度优先搜索在搜索树中又叫按层次遍历。对于搜索树而言，广度优先搜索的思路可以描述为：依次访问根结点的每一个子结点（第二层结点），再通过这些结点访问第三层结点…......
  • BFS广度优先搜索例题分析
    洛谷P1162填涂颜色题目描述由数字\(0\)组成的方阵中，有一任意形状闭合圈，闭合圈由数字\(1\)构成，围圈时只走上下左右\(4\)个方向。现要求把闭合圈内的所有空间都填写......
  • DFS深度优先搜索例题分析
    洛谷P1596LakeCountingS题面翻译由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个\(N\timesM(1\timesN\times100,1\leqM\leq100)\)的网格图......
  • 队列
    一、队列的基本概念1、队列的定义队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（FirstInFirstOut）的线性表，简称FIFO。允许......
  • day 22- 线程的礼让，优先级，守护线程
    线程的礼让利用Thread.yield()使线程进行礼让礼让的概念：礼让线程，让当前正在执行的线程暂停，但并不是阻塞将线程从运行状态转化为就绪状态线程礼让是由cpu调度，并......
  • 栈、队列、符号表
    栈概述生活中的栈存储货物或供旅客住宿的地方，可引申为仓库、中转站。例如我们现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99