堆结构和堆排序

2023-12-11 13:15:03

堆(优先队列)

时间复杂度:

初始化建堆的时间复杂度为 O(n)

堆排序重建堆 O(nlogn)

PriorityQueue小顶堆

小顶堆:任意一个非叶子节点的权值，都不大于其左右子节点的权值

构造函数

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛 IllegalArgumentException异常
PriorityQueue(Collection c)	用一个集合来创建优先级队列

也可以在初始化的时候指定comparator接口的实现,

常用api

函数名	功能介绍
boolean offer(E e)	插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException 异常，时间复杂度 O ( l o g 2 N ) O(log_2N) O(log2N)，注意：空间不够时候会进行扩容
E peek()	获取优先级最高的元素，如果优先级队列为空，返回null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空 boolean
isEmpty()	检测优先级队列是否为空，空返回true

特性:

PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的
PriorityQueue中存储的对象必须要能够比较大小,如果不能比较大小就会抛出ClassCaseException异常.
不能插入null对象,否则抛出NullPointerException
带有自动扩容机制
插入和杀出的时间复杂度为
O ( l o g 2 N ) O(log_2N) O(log2N)
底层使用了堆

扩容的过程 jdk1.8

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

从扩容方法上可以看出

如果容量小于64使用oldCapacity+oldCapacity+2的方式
如果容量大于64使用oldCapacity+(oldCapacity>>1)的方式(相当于1.5倍扩容)

底层数据结构

堆的概念

将一个关键码的集合k={k,k1,k2,k3…kn-1}把它的所有元素按照完全二叉树的顺序方式存储在数组中

在一个一维数组中

满足ki<=k2i+1 且 ki<=k2i+2的称为小堆
满足ki>=k2i+1 且 ki>=k2i+2的称为大堆

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

性质:

堆中某个节点的值总是不大于或者不小于父节点的值
堆总是一个完全二叉树

如果i为0,则i表示的节点为根节点,否则i节点的双亲为(i-1)/2
如果2*i+1小于节点个数,则节点i的左孩子下标为2*i+1,否则没有左孩子
如果2*i+2小于节点个数,则节点i的右孩子下标为2*i+2,否则没有右孩子

向上调整

向上调整的过程(最小堆)

先设定倒数第一个叶子节点为当前节点,标记为cur,找出他的父节点,用parent来标记
比较paren和cur的值,如果cur比parent小.则不满足小顶堆的规则,需要进行交换. 如果cur比parent大就不交换,此时调整结束.
如果不满足条件交换后, cur就重设为父节点下标,重新开始循环.然后检测是否满足最小堆的性质,一直到满足条件或者cur小于等于0结束.

向下调整

首先设定根节点为当前节点标记为cur,比较左右子树的值,找出更小的值,用child来标记.
比较child和cur的值,如果child比cur小,则不满足小堆的规则,需要进行交换.如果cur比parent大就不交换.此时调整结束
如果不满足条件交换后, cur就重设为子节点下标,重新开始循环.然后检测是否满足最小堆的性质,一直到满足条件或者cur小于等于0结束.

堆的创建(向上调整)

当有了个一个数组,但是不满足堆的结构要求,我们要从倒数第一个非叶子节点的子树开始调整,一直到根节点的树.

ArrayList<Integer> integers = new ArrayList<>();
        integers.add(95);
        integers.add(9);
        integers.add(14);
        integers.add(48);
        integers.add(29);
        integers.add(53);
        integers.add(0);
//        integers.add(5);
        PriorityQueue<Integer> queue1 = new PriorityQueue<>(integers);

初始arraylist数组元素转化为完全二叉树为上图这种形态.

堆的调整

其中关键方法有两个

    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

传入参数将size进行无符号右移 >>>1 并 -1

>>> 无符号右移 :

右移后左边空出的位用零来填充。移出右边的位被丢弃

初始的size为7(0111),经过运算后传入的参数i为3(0011)-1=2

 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; // assume left child is least
            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;
    }

从调试过程来看

half为3
k为上一个方法传入参数i,值为2
child为(k<<1 +)1 = 5 , reght为6,分别代表

左移的规则只记住一点：丢弃最高位，0补最低位

堆的插入

插入过程就是将数据插入到数组的最后,然后进行向上调整

假设再添加元素5之前,堆中已经有了这些元素.
现在添加元素5

 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;
    }

首先k的值为7,为将要插入元素的下标,满足条件>0进入while循环
父节点parent元素的下标为 (k-1)>>>1 为 3,所对应元素e的值为48
接着使用compareTo方法进行比较,e和将要插入元素key进行比较(ascII表)
父节点元素48较大,compareTo方法返回一个负数(返回第一个字符的ASCII码差值),
所以将父节点元素先下移,设置k的值为父节点下标,为将要插入元素的下标,然后进行下一次循环判断,直到到达堆顶结束循环.
然后将key值放置在堆中相应位置

堆的删除

堆的删除是值,删除堆顶的数据.过程为将堆顶的数据和最后一个数据进行交换,然后删除最后一个数据,进行向下调整算法.

堆排序

升序–大顶堆

将待排序序列构造成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n-1个元素的次小值。如此反复执行，便能得到一个有序序列了。

package 课堂代码.数据结构.课件练习.堆;

public class MyHeaphigh {

    int[] queue = new int[1000];
    int size = 0;

    //堆排序
    public void hepsort(int[] array) {
        createheap(array);
        for (int i = 0; i < queue.length - 1; i++) {
            size--;
            swap(0, size);
            shftdown(0);
        }
        size = array.length;
    }

    //将数组调整成堆
    public void createheap(int[] array) {
        queue = array;
        size = array.length;
        for (int i = (queue.length - 2) >> 1; i >= 0; i--) {
            shftdown(i);
        }
    }

    //添加元素offer
    // 向上调整的
    public boolean offer(int e) {
        int i = this.size;
        this.size = i + 1;
        queue[i] = e;
        shftup(i);
        return true;
    }

    //大顶堆升序

    //向下调整
    private void shftdown(int parent) {
        /**
         * 第一步算出左子节点和右子节点,选出最小的当做子节点
         * 将父节点和子节点进行交换,从子节点开始循环
         */
        int left = parent * 2 + 1, right;
        while (left < size) {
            right = left + 1;
            if (right < size && queue[left] < queue[right]) {
                left++;
            }
            if (queue[parent] > queue[left]) {
                break;
            } else {
                swap(parent, left);
            }
            parent = left;
            left = parent * 2 + 1;
        }
    }

    //向上调整
    private void shftup(int child) {
        while (child > 0) {
            int parent = (child - 1) >> 1;
            if (queue[parent] > queue[child]) {
                break;
            } else {
                swap(child, parent);
                child = parent;
            }
        }
    }

    //删除元素remove
    public void remove() {
        //删除的元素就为栈顶元素
        // 首先将栈顶元素和最后一个进行交换,然后向下调整
        swap(0, --size);

        shftdown(0);
    }


    private void swap(int left, int right) {
        int temp = queue[left];
        queue[left] = queue[right];
        queue[right] = temp;
    }
}
//排序

降序–小顶堆

package 课堂代码.数据结构.课件练习.堆;

public class MyHeaplow {
    int[] queue = new int[1000];
    int size = 0;

    //堆排序
    public void hepsort(int[] array){
        createheap(array);
        for (int i = 0; i < queue.length-1; i++) {
            size--;
            swap(0,size);
            shftdown(0);
        }
        size=array.length;
    }

    //将数组调整成堆
    public void createheap(int[] array) {
        queue = array;
        size = array.length;
        for (int i = (queue.length-2)>>1; i >=0 ; i--) {
            shftdown(i);
        }
    }

    //添加元素offer
    // 向上调整的
    public boolean offer(int e) {
        int i = this.size;
        this.size = i + 1;
        queue[i] = e;
        shftup(i);
        return true;
    }

    //小顶堆降序
    //向下调整
    private void shftdown(int parent) {
        /**
         * 第一步算出左子节点和右子节点,选出最小的当做子节点
         * 将父节点和子节点进行交换,从子节点开始循环
         */
        int left = parent * 2 + 1, right;
        while (left < size) {
            right = left + 1;
            if (right < size && queue[left] > queue[right]) {
                left++;
            }
            if (queue[parent] < queue[left]) {
                break;
            } else {
                swap(parent, left);
            }
            parent = left;
            left = parent * 2 + 1;
        }
    }

    //向上调整
    private void shftup(int child) {
        while (child > 0) {
            int parent = (child - 1)>>1;
            if (queue[parent] < queue[child]) {
                break;
            } else {
                swap(child, parent);
                child = parent;
            }
        }
    }

    //删除元素remove
    public void remove() {
        //删除的元素就为栈顶元素
        // 首先将栈顶元素和最后一个进行交换,然后向下调整
        swap(0,--size);
//        queue[0] = queue[--size];
        shftdown(0);
    }


    private void swap(int left, int right) {
        int temp = queue[left];
        queue[left] = queue[right];
        queue[right] = temp;
    }
}

大顶堆对应降序和小顶堆对应升序,其中变化的只有元素进行对比的时候使用的比较方法.

topk问题

什么是topk问题呢,下面举几个例子

给定 100 个 int 数字，在其中找出最大的 10 个；
给定 10 亿个 int 数字，在其中找出最大的 10 个（这 10 个数字可以无序）；
给定 10 亿个 int 数字，在其中找出最大的 10 个（这 10 个数字依次排序）；
给定 10 亿个不重复的 int 数字，在其中找出最大的 10 个；
给定 10 个数组，每个数组中有 1 亿个 int 数字，在其中找出最大的 10 个；
给定 10 亿个 string 类型的数字，在其中找出最大的 10 个（仅需要查 1 次）；
给定 10 亿个 string 类型的数字，在其中找出最大的 k 个（需要反复多次查询，其中 k 是一个随机数字）。

解决问题的思路是什么呢?

分而治之/hash映射 + hash统计 + 堆/快速/归并排序；
双层桶划分
Bloom filter/Bitmap；
Trie树/数据库/倒排索引；
外排序；
分布式处理之Hadoop/Mapreduce。

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

题目分析

这个问题就可以使用第一种方法,分而治之/hash映射 + hash统计 + 堆/快速/归并排序.

首先对于海量数据我们的内存肯定是存储不下的,那我们可以采取hash映射取模映射,将大文件分解为小文件,
然后使用HashMap结构进行频率统计
当每个小文件的频率统计完成之后,便可以采取堆排序或者快排,得到次数最多的ip

其中进行具体分析

一文件分割

ip是32位的,所以最多有2^32次方个不同的ip,IPV4地址本质是一个32位的二进制串,一个int也是四个字节32个bit位,所以我们可以使用int来存储ip,

对于一个ipv4地址来说:192.168.1.3

如果字节去除小数点用int来存储的话,ipv4最大为255255255255,而int值范围为 -2^31-231-1,即-2147483648-2147483647。显然是存储不下的,所以我们得采取其他办法来进行存储.

首先将ip地址进行分割,为192 168 1 3这样的形式,然后转化为二进制然后进行链接,结果为 192(10) = 11000000(2) ; 168(10) = 10101000(2) ; 1(10) = 00000001(2) ; 3(10) = 00000011(2)

对应转化为int值为-1062731775

这样就能存储到int类型的变量中了

或者将其存入long类型变量.然后对其取模1000的操作,从而将整个大文件分为1000个小文件.(有时候ip的分布并不是那么均匀,所以可能需要对其进行多次划分)

对于这样的文件再划分后具有这样的特征,如果划分了n个文件

同一个ip的所有记录就会被存储在一个文件中
每个文件所覆盖的ip最多有2^32/n个

二统计

当文件被分割到能够被内存存储之后,可以使用HashMap<Integer,Long>这样的数据结构来进行统计,

三排序

将每个分割的小文件进行堆排序(本题只要求最多的,可以使用遍历),选出现次数最多的元素,然后将结果存在另一个合适的地方,在所有小文件排序完成后,我们将会有n个键值对,然后在进行排序即可.

2.搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。从中找出搜索最热门的10个字符串

题目分析

假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

一统计

因为查询的字符串重复度比较高,所以对数据集进行一个估计如果最后重复的结果集小的话可以不进行划分,而是直接使用hashmap进行统计

二排序

最后进行堆排序,建立一个10大小的小顶堆,将数据进行一个遍历,找出value最大的十个key.

3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

题目分析

内存为1M,所以我们为了能够处理这些数据,最少要分为1024个小文件才能存入内存,一个词为16字节,

码农公寓

堆(优先队列)

时间复杂度:

PriorityQueue小顶堆

构造函数

常用api

特性:

扩容的过程 jdk1.8

底层数据结构

堆的概念

性质:

向上调整

向下调整

堆的创建(向上调整)

堆的插入

堆的删除

堆排序

升序–大顶堆

降序–小顶堆

topk问题

解决问题的思路是什么呢?

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

题目分析

其中进行具体分析

一 文件分割

二 统计

三 排序

2.搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。从中找出搜索最热门的10个字符串

题目分析

一 统计

二 排序

3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

题目分析

相关文章

一文件分割

二统计

三排序

一统计

二排序