二叉堆结构、堆排序、优先队列、计数器

2022-1-16

 

写在前面

  • 关于文章

    本系列文章主要根据算法大神左神（左程云）的算法与数据结构基础教程进行整理的，这里文章主要学习了有二叉堆结构、堆排序、计数器、优先队列结构、桶排序等。这里只是基于Java的相关代码实现。

二叉堆

什么是二叉堆

二叉堆本质就是一种完全二叉树。

完全二叉树：对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。

完全二叉树最重要的性质：如果n个节点的完全二叉树的节点按照层次并按从左到右的顺序从0开始编号，对于人一个绩点都有：

  • 序号为0的节点是根
  • 对于i>0，其父节点的编号为(i-1)/2。
  • 若2·i+1<n，其左子节点的序号为2·i+1，否则没有左子节点。
  • 若2·i+2<n，其右子节点的序号为2·i+2，否则没有右子节点。

二叉堆可以分为两种类型：小顶堆和大顶堆。也叫最大堆和最小堆。

最大堆

最大堆就是在一颗完全二叉树中的任何一个父节点的值，都大于或者等于它左右孩子节点的值。

最小堆

最小堆就是在一颗完全二叉树中的任何一个父节点的值，都小于或者等于它左右孩子节点的值。

二叉堆的根节点叫做堆顶。根据最大、小堆概念可以得知：堆顶在整颗完全二叉树中是最大或最小的元素。

二叉堆是堆排序和优先队列的基础。

二叉堆操作

对于二叉堆，有如下几种操作：

  • 插入节点
  • 删除节点
  • 构建二叉堆

这几种操作都是基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整为一个堆。以最小堆为例，讲解二叉堆事如何进行自我调整的。

插入节点

  • 当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。
  • 此时，若新节点的父节点比新节点大，显然不符合最小堆的性质。于是让新节点“上浮”，和父节点交换位置。
  • 继续用新节点和其父节点做比较，若新节点的父节点比新节点大，则让新节点继续“上浮”。
  • 继续比较，最终新节点“上浮”，到了合适位置。

删除节点

  • 二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。
  • 此时，为了继续维持完全二叉树的结构，我们把堆最后一个节点临时补到原本堆顶的位置。
  • 接下来，让暂处堆顶位置的节点和它的左、右孩子进行比较，如果左、右孩子节点中最小的一个比父节点小，那么让父节点“下沉。
  • 继续让父节点和它的左、右孩子做比较。

构建二叉堆

构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次“下沉”。

 

时间复杂度

插入节点：时间复杂度是O(logn);是单一节点的"上浮"，平均交换次数都是堆高度的一半。 空间复杂度O(n)

删除节点：时间复杂度是O(logn);删除操作是针对单节点的"下沉",平均交换次数都是堆高度的一半。空间复杂度O(n)

 

代码实现

二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。

因此，二叉堆的所有节点都存储在数组中。

在数组中，在没有左、右指针的情况下，如何定位一个父节点的左孩子和右孩子呢？采用数组下标来计算。

假设父节点的下标是parent,那么它的左孩子下标就是2xparent+1;右孩子下标就是2xparent+2.

/**
* “上浮”调整
* param array. 待调整的堆
*/
public static void upAdjust(int[] array){
  int childIndex=array.length-1;
  int parentIndex=(childIndex-1)/2;
  // temp保存插入的叶子节点值，用于最后的赋值
  int temp=array[childIndex];
  while(childIndex >0 && temp< array[parentIndex]){
    // 无须真正交换，单向赋值即可
    array[childIndex]=array[parentIndex];
    childIndex=parentIndex;
    parentIndex=(parentIndex-1)/2;
  }
  array[childIndex]=temp;
}

/** 
* “下沉”调整
* param array   待调整的堆
* param parentIndex 要“下沉”的父节点
* param length 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex,int length){
  // temp保存父节点值，用于最后的赋值
  int temp =array[parentIndex];
  int childIndex=2*parentIndex+1;
  while(childIndex<length){
    //如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
    if(childIndex+1<length && array[childIndex+1]<array[childIndex]){
      childIndex++;
    }
    //如果父节点小于任何一个孩子的值，则直接跳出
    if(temp<=array[childIndex]){
      break;
    }
    //无须真正交换，单向赋值即可
    array[parentIndex]=array[childIndex];
    parentIndex=childIndex;
    childIndex=2*childIndex+1;
  }
  array[parentIndex]=temp;
}

/** 
* 构建堆
* param  array 待调整的堆
*/
public static void buildHeap(int[] array){
  // 从最后一个非叶子节点开始，依次做"下沉"调整
  for(int i=(array.length-2)/2;i>=0;i--){
    downAdjust(array,i,array.length);
  }
}

public static void main(String[] args){
  int[] array=new int[]{1,3,2,6,5,7,8,9,10,0};
  upAdjust(array);
  System.out.println(Arrays.toString(array));
  
  array=new int[]{7,1,3,10,5,2,8,9,6};
  buildHeap(array);
  System.out.println(Arrays.toString(array));
}

 

堆排序

算法步骤

  1. 创建一个堆 H[0……n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
  4. 重复步骤 2，直到堆的尺寸为 1。

把无序数组构建成二叉堆。循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

动图演示

img

img

算法分析

时间复杂度为O(NlogN)，空间复杂度为O（1）

代码实现

	/**
     * 推排序入口方法
     * @param arr
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 将数组全部元素构成堆结构
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        // 
        int size = arr.length;
        // 将堆结构中最后一个元素与堆顶置换
        swap(arr, 0, --size);
        // 循环将数组中各个元素都与堆顶置换进行重新构建堆结构，以便找到最值
        while (size > 0) {
            heapify(arr, 0, size);
            // --size因为每次可以确定一个元素的最终位置
            swap(arr, 0, --size);
        }
    }

    /**
     * 将新插入的元素值放到正确的位置 构成大顶堆结构
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        // 当元素值大于其父节点元素值时
        while (arr[index] > arr[(index - 1) / 2]) {
            // 交换二者
            swap(arr, index, (index - 1) /2);
            // 更新元素当前的下标
            index = (index - 1)/2 ;
        }
    }

    /**
     * 将堆顶元素”下沉“
     * @param arr 待排序数组
     * @param index 堆顶元素下标
     * @param size 元素个数，防止下标溢出
     */
    public static void heapify(int[] arr, int index, int size) {
        // 获取左孩子下标
        int left = index * 2 + 1;
        // 当有左孩子时
        while (left < size) {
            // 比较左右孩子的值，获取二者的较大值的元素下标
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            // 比较左右孩子较大者是否比父节点大
            largest = arr[largest] > arr[index] ? largest : index;
            // 如果相等 则跳出无需继续向下比较
            if (largest == index) {
                break;
            }
            // 如果不相等 则交换两者的值
            swap(arr, largest, index);
            // 更新根节点的下标值
            index = largest;
            // 更新左孩子的下标值
            left = index * 2 + 1;
        }
    }

    /**
     * 交换数组中两元素值的方法
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

 

优先级队列

什么是优先队列

队列的特点：先进先出（FIFO）,入队列，将新元素置于队尾；出队列，队头元素最先被移出。

什么是优先队列？
优先队列不再遵循先进先出的原则，而是分为两种情况。-

  • 最大优先队列：无论入队顺序如何，都是当前最大的元素优先出队。
  • 最小优先队列：无论入队顺序如何，都是当前最小的元素优先出队。

要实现优先队列，利用线性数据结构并非不能实现，但时间复杂度较高。可以采用二叉堆实现。

优先队列的实现

我们知道二叉堆的特性：

  • 最大堆的堆顶是整个堆中的最大元素
  • 最小堆的堆顶是整个堆中的最小元素

因此可以采用，最大堆来实现最大优先队列，这样的话，每次入队操作就是堆的插入操作，每次出队操作就是删除堆顶节点。

时间复杂度

优先队列的入队和出队操作，时间复杂度是多少？

因为二叉堆节点“上浮”和“下沉”的时间复杂度都是O(logn);所以优先队列入队和出队的时间复杂度都是O(logn).

在Java中有一个PriorityQueue类底层就是使用堆结构写的优先级队列。

PriorityQueue<Integer> heap = new PriorityQueue<>();

 

总结

什么是树

树是n个节点的有限集合，有且仅有一个特定的称为根的节点，当n>1时，其余节点可以分为m个互不相交的有限集合，每一个集合本身右是一个树，并称为根的子树。

什么是二叉树？

二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树、满二叉树两种特殊形式。

二叉树的遍历方式

根据遍历节点之间的关系，可以分为前序遍历、中序遍历、后序遍历、层序遍历几种方式；从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历

什么是二叉堆

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。

在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。

在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。

什么是优先队列

优先队列分为最大优先队列和最小优先队列。

最大优先队列： 无论入队顺序如何，当前最大的元素都会优先出队列，基于最大堆实现。

最小优先队列：无论入队顺序如何，当前最小的元素都会优先出队，基于最小堆实现。

 

比较器

1）比较器的实质就是重载比较运算符

2）比较器可以很好的应用在特殊标准的排序上

3）比较器可以很好的应用在根据特殊标准排序的结构上

public class Comparator {

    // 内部类
	public static class Student {
		public String name;
		public int id;
		public int age;

		public Student(String name, int id, int age) {
			this.name = name;
			this.id = id;
			this.age = age;
		}
	}

    // 比较器
	public static class IdAscendingComparator implements Comparator<Student> {

		@Override
		public int compare(Student o1, Student o2) {
			return o1.id - o2.id;
		}

	}

	public static class IdDescendingComparator implements Comparator<Student> {

		@Override
		public int compare(Student o1, Student o2) {
			return o2.id - o1.id;
		}

	}
    
    public static void printStudents(Student[] students) {
		for (Student student : students) {
			System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
		}
	}
    
    public static void main(String[] args) {
		Student student1 = new Student("A", 2, 23);
		Student student2 = new Student("B", 3, 21);
		Student student3 = new Student("C", 1, 22);

		Student[] students = new Student[] { student1, student2, student3 };

		Arrays.sort(students, new IdAscendingComparator());
		printStudents(students);
    }

 

微信关注

WeChat

 

阅读剩余
版权声明：
作者：理想
链接：https://www.imyjs.cn/archives/512
文章版权归作者所有，未经允许请勿转载。
THE END
Git简易的命令行入门教程
<<上一篇
【操作系统】OS概念、分类、功能、发展、结构
下一篇>>
相关推荐
什么是SAN和NAS？两者有啥区别？
Linux系统中的系统盘和数据盘是什么意思？
【MySQL面试】Java工程师面试必备的MySQL题目
【计算机网络】别再问我TCP的三次握手和四次挥手啦！
C语言实现链表增、删、改、查基本操作
【数据库原理】DB基本概念、发展、研究领域
【操作系统】浅谈死锁的产生、预防、避免、检测与解除
【操作系统】OS资源管理之设备管理
本站由 提供加速服务 编程那点事儿     编程那点事儿 编程那点事儿