你真的熟悉堆排序吗?

简介: 你真的熟悉堆排序吗?


1.SpringBoot 整合篇


2. 手写一套迷你版HTTP服务器


3.记住:永远不要在MySQL中使用UTF-8


4. Springboot启动原理解析


什么是堆


堆的基本特点有以下两项:


  1. 堆是一棵完全二叉树或者是近似完全二叉树


  1. 堆里面的每个父节点都要大于或等于(或者小于等于)其子树节点的每个节点值。


image.png


什么是完全二叉树


要求除了最后一层以外,其余层的节点都要是满的。


大顶堆


每个节点的值都大于其子节点的值,我们通常称之为大顶堆。


小顶堆


每个节点的值都小于其子节点的值,我们通常称之为小顶堆。


那么我们该如何来进行一个堆的构建呢?


先别急,我们来了解以下的几个概念先:


堆的存储方式


image.png


如上图所示,当我们对一个堆进行节点数据存储的时候,将每个节点的值都按照二叉树从上到下,从左到右的顺序存储到数组里面去。拿图中的6号节点来看(暂时命名数组为arr),它的存储位置是arr[6],它的父亲节点为arr[3],如果你有细心发现的话,会发现父子节点之间的编号存在有以下的关系:


  • leftNo = parentNo * 2
  • rightNo = parentNo * 2 + 1
  • parentNo = (nodeNo) / 2


这三个规律在下文中会涉及到。


向上堆化


所谓的向上堆化,是指在构建堆的过程中,当一个节点的值大于其父节点的值的时候,就会发生节点值的交换,直至当前节点的值小于或等于父节点的值。如下图所示:


图中有一个初始化的堆,现在需要往堆里面插入一个新的元素39。


image.png


image.png


所有的比较节点完毕之后,就会如上图所示


向下堆化


所谓的向下堆化,是指在构建堆的过程中,当一个节点的值小于其父节点的值的时候,就会发生节点值的交换,直至当前节点的值大于或等于父节点的值。


同样我们结合图片的形式来进行描述:


图中有一个初始化的堆结构,然后现在需要进行节点的插入操作

新插入的节点8位于1号索引的位置,然后依次进行向下堆化处理


image.png


所有的比较节点完毕之后,就会如上图所示


在建堆(大顶堆)完成之后,数组中的堆顶元素通常都是最大的元素,这个时候,我们只需要将堆顶的元素进行移除,就能获取到当前数组的最大元素了。但是新的问题又来了,如何进行对于堆顶元素的弥补呢?


这个时候我们会将存储节点的数组的最后一个元素弥补到头部节点处,然后从上往下进行向下堆化处理,不断的重复堆顶元素移除,弥补头结点,向下堆化,不断的循环这段操作。


基于大顶堆的排序完整代码

/**
 * @author idea
 * @data 2019/2/19
 */
public class TopHeap {
    private int[] arr;
    private int maxSize;
    private int count;
    public TopHeap(int size) {
        this.arr = new int[size];
        this.maxSize = size;
        this.count = 0;
    }
    /**
     * 添加元素
     *
     * @param data
     */
    private void add(int data) {
        if (count > maxSize) {
            return;
        }
        count++;
        arr[count] = data;
        int i = count;
        //向上堆化
        while (i / 2 > 0 && arr[i] > arr[i / 2]) {
            swap(arr, i, i / 2);
            i = i / 2;
        }
    }
    /**
     * 删除节点
     *
     * @return
     */
    private int removeNode() {
        if (count < 0) {
            return -1;
        }
        int result = arr[1];
        arr[1] = arr[count];
        count--;
        //向下堆化
        heapify(arr, count, 1);
        return result;
    }
    /**
     * 排序
     *
     * @return
     */
    public int[] sort() {
        int[] result = new int[count];
        int size = count;
        for (int j = 0; j < size; j++) {
            result[j] = removeNode();
        }
        return result;
    }
    /**
     * 堆化
     *
     * @param arr   数组
     * @param total 数组总长度
     * @param i     指堆化的开始索引值
     */
    private void heapify(int[] arr, int total, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= total && arr[i] < arr[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= total && arr[maxPos] < arr[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i) {
                break;
            }
            swap(arr, i, maxPos);
            i = maxPos;
        }
    }
    /**
     * 交换数组元素值
     *
     * @param arr
     * @param n
     * @param k
     */
    private void swap(int[] arr, int n, int k) {
        int temp = arr[n];
        arr[n] = arr[k];
        arr[k] = temp;
    }
    public static void main(String[] args) {
        int[] arr=new int[]{12, 3, -45, 234, 123, 12, 55, 33};
        TopHeap topHeap = new TopHeap(12);
        for (int i : arr) {
            topHeap.add(i);
        }
        int[] res = topHeap.sort();
        for (int re : res) {
            System.out.print(re + " ");
        }
    }
}


堆在java应用中的具体实践


java里面的优先级队列PriorityQueue的底层操作很多都是基于了堆进行排序的,我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。


例如说当在某个特殊的应用场景中,需要对居民的年龄进行排序操作,那么这个时候可以通过使用PriorityQueue来对每一个Person对象的年龄进行排序,然后进入队列进行年龄的从小到大的排序处理。


import java.util.PriorityQueue;
/**
 * @author idea
 * @date 2019/5/15
 */
class Person implements Comparable<Person> {
    public int age;
    Person(int age) {
        this.age = age;
    }
    @Override
    public int compareTo(Person other) {
        return other.age - age;
    }
    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                '}';
    }
}
public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Person> queue = new PriorityQueue<>();
        Person person1 = new Person(31);
        Person person2 = new Person(22);
        Person person3 = new Person(65);
        Person person4 = new Person(15);
        Person person5 = new Person(28);
        /**
         * offer 插入新的元素 插入失败会返回false
         * add 插入新的元素 插入失败会抛异常
         */
        queue.offer(person1);
        queue.offer(person2);
        queue.offer(person3);
        queue.offer(person4);
        queue.offer(person5);
        int size = queue.size();
        /**
         * element 会弹出队首元素,但是并不会删除
         * peek 会弹出队首元素,但是也不会删除
         */
        for (int i = 0; i < size; i++) {
            /**
             * remove 移除队首元素 失败会抛异常
             * poll 移除队首元素 失败会返回null
             */
            Person person = queue.poll();
            System.out.println(person.toString());
        }
    }
}


深入源码来看offer操作


public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            //插入元素之后需要进行向上堆化处理
            siftUp(i, e);
        return true;
    }
  private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }
  //向上堆化的核心部分
    @SuppressWarnings("unchecked")
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            //通过比较器进行比对
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        //堆顶元素插入
        queue[k] = key;
    }


poll操作的源码部分:


public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
        //向下堆化处理
            siftDown(0, x);
        return result;
    }
  private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }
       //向下堆化处理
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
                //找到左右节点里面相对较小的那个节点
            int child = (k << 1) + 1; 
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                 ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
                //比较器比较元素的大小
            if (key.compareTo((E) c) <= 0)
                break;
                //取代原来节点的值
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }


有几点地方我们需要注意一下:



  1. PriorityQueue 不允许空值,而且不支持 non-comparable(不可比较)的对象,如果传入的对象是用户自定义的这类对象,队列要求该对象使用Java Comparable 和 Comparator 接口给对象排序,然后再按照优先级来进行对于元素的处理。


  1. PriorityQueue 的大小是不受限制的,但在创建时可以指定初始大小。当我们向优先队列增加元素的时候,队列大小会自动增加。


  1. PriorityQueue 是非线程安全的,所以 Java 提供了 PriorityBlockingQueue(实现 BlockingQueue接口)用于Java 多线程环境。


总体小结


  1. 堆排序在使用的时候整体的过程都是基于两个元素进行不断的比较操作,而且对于原本已经有序的数组而言,通常在初始化建立堆结构的时候,容易将原本已经有序的数据给打乱,因此数据的交换次数会较多。


  1. 堆里面比较重要的两个操作插入和删除操作都会使用到堆化的这么一个步骤,删除堆顶数据的时候,我们把数组中的最后一个元素放到堆顶,然后从上往下堆化。这两个操作时间复杂度都是 O(logn)O(log⁡n)。


  1. 通常我们在进行排序的时候都会优先选择使用快速排序之类的方法,但是在遇到一些和排序没有太大关联的问题的时候,例如说TopN类型的经典问题,这时候堆排序的优势就出来了。用堆排序可以在N个元素中找到top K,时间复杂度是O(N log K),空间复杂的是O(K),而快速排序的空间复杂度是O(N),在这种场景中,使用堆排序会更加适合。



目录
相关文章
|
6月前
|
算法 Python
数据结构算法--4堆排序
堆排序过程概述:建立大根堆,将堆顶最大元素移出并替换为末尾元素,调整保持堆性质,重复此过程直至堆为空,实现排序。时间复杂度为O(nlogn)。Python中可用heapq模块进行堆操作。
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
22 0
数据结构与算法学习十四:常用排序算法总结和对比
|
2月前
|
算法 搜索推荐
数据结构与算法学习十八:堆排序
这篇文章介绍了堆排序是一种通过构建堆数据结构来实现的高效排序算法,具有平均和最坏时间复杂度为O(nlogn)的特点。
74 0
数据结构与算法学习十八:堆排序
|
6月前
|
搜索推荐 算法 大数据
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
​【数据结构与算法】冒泡排序:简单易懂的排序算法解析
|
7月前
|
算法 搜索推荐
数据结构与算法⑫(第四章_中_续一)堆排序(详解)
数据结构与算法⑫(第四章_中_续一)堆排序(详解)
44 0
|
搜索推荐
[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序
[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序
|
存储 搜索推荐
[数据结构 -- 手撕排序算法第四篇] 堆排序,一篇带你搞懂堆排序
[数据结构 -- 手撕排序算法第四篇] 堆排序,一篇带你搞懂堆排序
|
7月前
|
机器学习/深度学习 搜索推荐 算法
程序员必须掌握的排序算法:希尔排序的原理与实现
程序员必须掌握的排序算法:希尔排序的原理与实现
99 1
|
7月前
|
机器学习/深度学习 搜索推荐 算法
程序员必须掌握的排序算法:插入排序的原理与实现
程序员必须掌握的排序算法:插入排序的原理与实现
120 1
|
7月前
|
存储 算法 C语言
【408数据结构与算法】—堆排序(二十一)
【408数据结构与算法】—堆排序(二十一)
【408数据结构与算法】—堆排序(二十一)