目录

一.概念

二.堆中最重要三个方法

三.大顶堆

四.基于数组实现大顶堆

五.堆排序

六.小顶堆

七.基于数组实现小顶堆

八.ProiorityQueue和Heap

 示例:

九.求数组中第K大元素

十.求数据流中第K大元素

十一.求数据流的中位数


一.概念

  堆(Heap)在计算机科学中是一种数据结构,用于存储和管理动态分配的内存。堆的主要特点是它是一个有序的完全二叉树,每个节点的值都大于小于其子节点的值,称为最小堆最大堆

堆常用于实现优先队列堆排序图算法等。堆排序是一种基于堆数据结构的排序算法,它具有稳定性和不需要额外的内存空间的优点。优先队列是一种数据结构,支持插入和删除最大或最小元素的操作,并根据优先级对元素进行排序。堆可以用于高效地实现优先队列。

同时,堆还有其他用途,比如内存管理中的动态内存分配,垃圾回收算法中的对象分配

二.堆中最重要三个方法

 1.heapify() 调整堆

    通过调整堆,可以让不符合堆特性的节点转化为符合堆特性的序列

 2.up() 上浮

   在offer()向末尾添加元素时,通过上浮操作,插入到合适的位置

 3.down() 下潜 

   在poll()方法从堆顶取出元素后,通过下潜方法,下潜到合适的位置

三.大顶堆

大顶堆(Max Heap)是一种堆的实现方式,它满足以下性质:

  1. 每个节点的值都大于或等于其子节点的值。
  2. 堆顶元素(根节点)是整个堆中最大的元素。

在大顶堆中,任意节点的值都大于或等于其子节点的值,但是它们之间的顺序并没有固定的要求,即左右子节点之间的大小关系并不要求一定是有序的。

大顶堆可以通过数组完全二叉树来实现。在数组中,堆的根节点存储在索引为0的位置,而任意节点i的左子节点存储在索引为2i+1的位置,右子节点存储在索引为2i+2的位置。

大顶堆的常见操作包括:

  1. 插入元素:将元素插入堆的底部,然后通过调整堆的结构将其置于正确的位置上,以保持堆的性质。
  2. 删除堆顶元素:将堆顶元素与堆底元素交换,然后删除堆底元素,再通过调整堆的结构将堆顶元素置于正确的位置上

四.基于数组实现大顶堆

package 堆;

import java.util.Arrays;
import java.util.Iterator;

/**
 * 大顶堆
 */
public class MaxHeap implements Iterable<Integer>{

    int[] array;
    int size;

    /**
     * 通过构造方法将任意数组调整为大顶堆
     * @param array
     */
    public MaxHeap(int[] array){
        this.array = array;
        this.size = array.length;
        this.heapify();
    }

    public MaxHeap(int capacity){
        this.array = new int[capacity+1];
        size = 0;
    }



    /**
     * 调整堆
     *  从最后一个非叶子节点开始,以此向前开始调整堆
     *  使其符合大顶堆的特性
     */
    public void heapify(){

        for (int i = size/2 -1 ; i>=0 ; i--) {
              down(i);
        }

    }

    /**
     * 添加元素,
     *  1.先添加到数组的末尾+1处 size处
     *  2.然后判断该处和他的父节点处元素大小,如果比他的父亲大,就交换二者,
     *     parent = (child-1) / 2
     *  3.然后将child置为parent,parent置为它的parent,以此往上走,
     *  4.两种情况:
     *     - (1)直到child为 0,这种是offered比所有的元素都大的情况
     *     - (2)直到child处元素不比parent处大,就是已经上浮到合适的位置了,
     *     退出循环
     *  5.将array[child]处赋值为offered
     *
     * @param offered
     * @return
     */
    public boolean offer(int offered){
        if(size == array.length){
            return false;
        }
        //上浮
        size++;
        up(offered);
        return true;
    }

    /**
     * 上浮
     * @param offered
     */
    public void up(int offered){
        //先找到末尾位置
        int child = size;
        //如果child>0,就继续上浮
        while (child > 0){
            //找到父节点
            int parent = (child - 1) / 2;
            //比较child和parent
            if(offered > array[parent]){
                //交换child和parent
                array[child] = array[parent];
            }else {
                break;
            }
            //交换完成一次之后,将child置为parent
            child = parent;
        }
          //上浮完成后,为array[child]处赋值
        array[child] = offered;
    }

    /**
     * 获取堆顶元素
     * @return 堆顶元素
     */
    public int peek(){
        if(size==0){
            return Integer.parseInt(null);
        }
        return array[0];
    }

    /**
     * 移除堆顶元素
     * @return 堆顶元素
     */
    public int poll(){
        if(size==0){
            return Integer.parseInt(null);
        }
        int top = array[0];
        //先交换堆顶和最后一个元素
        swap(0,size-1);
        size--;

        //从堆顶开始下潜
        down(0);

        return top;
    }

    /**
     * 移除指定位置处的元素
     * @param index 指定位置
     * @return index处元素
     */
    public int poll(int index){
        if(size==0){
            return Integer.parseInt(null);
        }
        int indexE = array[index];
        //先交换index处和最后一个元素
        swap(index,size-1);
        size--;
        //从index处开始下潜
        down(index);
        return indexE;
    }

    /**
     * 替换堆顶元素
     */
    public void replace(int replaced){
        if(size==0){
            throw new RuntimeException("堆为空!");
        }
        array[0] = replaced;
        //下潜
        down(0);
    }


    /**
     * 下潜操作
     * @param parent 最后一个非叶子节点
     */
    public void down(int parent){
        //找到该非叶子节点的左孩子和右孩子
        int left =  parent*2 + 1;
        int right = left + 1;
        //先假设parent是最大的
        int max = parent;
        //然后分别比较parent和left,right的大小
        if(left<size && array[max] < array[left]){
            max = left;
        }
        if(right<size && array[max] < array[right]){
            max = right;
        }
        /**
         * 如果max!=parent,说明孩子有比父亲大的,所以要交换二者,
         * 当交换后,堆结构可能会被破坏,所以要继续调整堆,使其所有节点
         * 都满足大顶堆的特性
         */
        if(max != parent){
            swap(max,parent);
            down(max);
        }
    }


    public void swap(int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }





    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int p = 0;
            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public Integer next() {
                int res = array[p];
                p++;
                return res;
            }
        };
    }
}

测试一下:

    public static void main(String[] args) {

        int[] array = {1,2,3,4,5,6,7};
        MaxHeap maxHeap = new MaxHeap(array);

        System.out.println(Arrays.toString(maxHeap.array));

        maxHeap.poll();

        System.out.print("[");
        for (Integer num : maxHeap) {
            System.out.print(num+",");
        }
        System.out.print("]");

    }

运行:

[7, 5, 6, 4, 2, 1, 3]
[6,5,3,4,2,1,]
进程已结束,退出代码0

可以看到满足大顶堆特性

五.堆排序

  可以利用大顶堆的特性,堆顶元素最大,实现堆排序,将无序数组调整为从小到大排序

 /**
     * 堆排序
     */
    @Test
    public void testHeapPaiXu(){
        int[] array = {3,1,6,2,7,4,9,1,3};
        MaxHeap heap = new MaxHeap(array);

        while (heap.size > 1){
            //先交换
            heap.swap(0,heap.size-1);
            //size减一
            heap.size--;
            //下潜调整堆
            heap.down(0);
        }

        System.out.println(Arrays.toString(heap.array));

    }

运行:


[1, 1, 2, 3, 3, 4, 6, 7, 9]

可以看到已经成功调整了排序

六.小顶堆

小顶堆(Min Heap)是一种堆的实现方式,它满足以下性质:

  1. 每个节点的值都小于或等于其子节点的值。
  2. 堆顶元素(根节点)是整个堆中最小的元素。

在小顶堆中,任意节点的值都小于或等于其子节点的值,但是它们之间的顺序并没有固定的要求,即左右子节点之间的大小关系并不要求一定是有序的。

小顶堆可以通过数组或完全二叉树来实现。在数组中,堆的根节点存储在索引为0的位置,而任意节点i的左子节点存储在索引为2i+1的位置,右子节点存储在索引为2i+2的位置。

小顶堆的常见操作包括:

  1. 插入元素:将元素插入堆的底部,然后通过调整堆的结构将其置于正确的位置上,以保持堆的性质。
  2. 删除堆顶元素:将堆顶元素与堆底元素交换,然后删除堆底元素,再通过调整堆的结构将堆顶元素置于正确的位置上。

小顶堆在各种算法和数据结构中也有广泛应用,和大顶堆类似。

七.基于数组实现小顶堆

  实现小顶堆和大顶堆类似,只需要把up和down中的比较符合改变即可:

package 堆;

import java.util.Iterator;

/**
 * 小顶堆
 */
public class MinHeap implements Iterable<Integer> {


    int[] array;
    int size;

    /**
     * 通过构造方法将任意数组调整为大顶堆
     * @param array
     */
    public MinHeap(int[] array){
        this.array = array;
        this.size = array.length;
        this.heapify();
    }


    public MinHeap(int capacity){
        this.array = new int[capacity+1];
        this.size = 0;
    }




    /**
     * 调整堆
     *  从最后一个非叶子节点开始,以此向前开始调整堆
     *  使其符合大顶堆的特性
     */
    public void heapify(){

        for (int i = size/2 -1 ; i>=0 ; i--) {
            down(i);
        }

    }

    /**
     * 添加元素,
     *  1.先添加到数组的末尾+1处 size处
     *  2.然后判断该处和他的父节点处元素大小,如果比他的父亲小,就交换二者,
     *     parent = (child-1) / 2
     *  3.然后将child置为parent,parent置为它的parent,以此往上走,
     *  4.两种情况:
     *     - (1)直到child为 0,这种是offered比所有的元素都小的情况
     *     - (2)直到child处元素不比parent处小,就是已经上浮到合适的位置了,
     *     退出循环
     *  5.将array[child]处赋值为offered
     *
     * @param offered
     * @return
     */
    public boolean offer(int offered){
        if(size == array.length){
            return false;
        }
        //上浮
        size++;
        up(offered);
        return true;
    }

    /**
     * 上浮
     * @param offered
     */
    public void up(int offered){
        //先找到末尾位置
        int child = size;
        //如果child>0,就继续上浮
        while (child > 0){
            //找到父节点
            int parent = (child - 1) / 2;
            //比较child和parent
            if(offered < array[parent]){
                //交换child和parent
                array[child] = array[parent];
            }else {
                break;
            }
            //交换完成一次之后,将child置为parent
            child = parent;
        }
        //上浮完成后,为array[child]处赋值
        array[child] = offered;
    }

    /**
     * 获取堆顶元素
     * @return 堆顶元素
     */
    public int peek(){
        if(size==0){
            return Integer.parseInt(null);
        }
        return array[0];
    }

    /**
     * 移除堆顶元素
     * @return 堆顶元素
     */
    public int poll(){
        if(size==0){
            return Integer.parseInt(null);
        }
        int top = array[0];
        //先交换堆顶和最后一个元素
        swap(0,size-1);
        size--;

        //从堆顶开始下潜
        down(0);

        return top;
    }

    /**
     * 移除指定位置处的元素
     * @param index 指定位置
     * @return index处元素
     */
    public int poll(int index){
        if(size==0){
            return Integer.parseInt(null);
        }
        int indexE = array[index];
        //先交换index处和最后一个元素
        swap(index,size-1);
        size--;
        //从index处开始下潜
        down(index);
        return indexE;
    }
    /**
     * 替换堆顶元素
     */
    public void replace(int replaced){
        if(size==0){
            throw new RuntimeException("堆为空!");
        }
        array[0] = replaced;
        //下潜
        down(0);
    }


    /**
     * 下潜操作
     * @param parent 最后一个非叶子节点
     */
    public void down(int parent){
        //找到该非叶子节点的左孩子和右孩子
        int left =  parent*2 + 1;
        int right = left + 1;
        //先假设parent是最大的
        int min = parent;
        //然后分别比较parent和left,right的大小
        if(left<size && array[min] > array[left]){
            min = left;
        }
        if(right<size && array[min] > array[right]){
            min = right;
        }
        /**
         * 如果min!=parent,说明孩子有比父亲小的,所以要交换二者,
         * 当交换后,堆结构可能会被破坏,所以要继续调整堆,使其所有节点
         * 都满足小顶堆的特性
         */
        if(min != parent){
            swap(min,parent);
            down(min);
        }
    }


    public void swap(int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }





    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int p = 0;
            @Override
            public boolean hasNext() {
                return p != size;
            }

            @Override
            public Integer next() {
                int res = array[p];
                p++;
                return res;
            }
        };
    }

}

八.ProiorityQueue和Heap

Java中自带的堆实现类包括PriorityQueueHeap,它们都是基于小顶堆的数据结构。

  1. PriorityQueue: PriorityQueue是Java中的优先队列类,它是通过小顶堆实现的。PriorityQueue可以自动将元素按照优先级进行排序,并保证每次操作的时间复杂度为O(logn)。
    PriorityQueue的常见方法包括:add(E e)、offer(E e):将元素插入队列;remove()、poll():删除并返回队列中的头元素;peek():返回队列中的头元素。

  2. Heap:Heap是Java中提供的用于实现堆数据结构的抽象类,它定义了一些基本的堆操作,如插入、删除元素,获取堆顶元素等。可以通过继承Heap类来实现自定义的堆。

 示例:

1.PriorityQueue的例子:

  

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个优先队列,默认是小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 使用offer方法插入元素到队列中
        pq.offer(5);
        pq.offer(3);
        pq.offer(8);
        pq.offer(1);
        pq.offer(9);

        // 使用poll方法获取并删除队列中的头元素
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

 输出结果:1 3 5 8 9

2.Heap的例子:

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class HeapExample {
    public static void main(String[] args) {
        // 创建一个堆
        List<Integer> heap = new Heap<>(Comparator.naturalOrder());

        // 使用offer方法插入元素到堆中
        heap.offer(5);
        heap.offer(3);
        heap.offer(8);
        heap.offer(1);
        heap.offer(9);

        // 使用poll方法获取并删除堆顶元素
        while (!heap.isEmpty()) {
            System.out.print(heap.poll() + " ");
        }
    }
}

 输出结果:1 3 5 8 9

请注意,Heap类并不是Java标准库中的一部分,它只是一个示例实现。在实际开发中,通常会使用PriorityQueue来实现堆的功能

九.求数组中第K大元素

package 堆;

/**
 * 求数组中第k大的元素
 */
public class L255_K_max {


    public static void main(String[] args) {

        int[] array = {1,4,2,6,3,9,5,10};

        int max = K_Max(array, 2);

        System.out.println(max);


    }

    /**
     *  思路:
     *   1.首先将前 k 个元素添加到堆中,调整为小顶堆
     *   2.然后从 k 处向后依次遍历:
     *   ->(1)如果 元素比堆顶元素小,就跳过
     *   -> (2) 如果元素比堆顶元素大,则替换堆顶元素
     *   3.最后遍历完成,返回堆顶元素,该元素就是第 K 大的元素
     * @param array
     * @param k
     * @return
     */
    public static int K_Max(int[] array,int k){

        MinHeap heap = new MinHeap(k);

        for (int i = 0; i < k; i++) {
            heap.offer(array[i]);
        }
        for(int i = k; i< array.length;i++){
            if(array[i] > heap.peek()){
                heap.replace(array[i]);
            }
        }
        return heap.peek();
    }




}

 运行:

9

进程已结束,退出代码0

十.求数据流中第K大元素

package 堆;

/**
 * 求数据流中第K大的元素
 */
public class L703_Stream_K_Max {

    private MinHeap heap;


    public L703_Stream_K_Max(int[] nums,int k){
        this.heap = new MinHeap(k);
        for (int num : nums) {
            add(num);
        }
    }

    public  int add(int val){
        //如果不满,先添加
        if(heap.size != heap.array.length-1){
            heap.offer(val);
        }else if( val > heap.peek() ){
            //满了,替换返回
             heap.replace(val);
        }
        return heap.peek();
    }


    public static void main(String[] args) {

        int nums[] = {1,2,6,3,11,5,9};
        L703_Stream_K_Max stream_k_max = new L703_Stream_K_Max(nums, 3);

        System.out.println(stream_k_max.add(2));
        System.out.println(stream_k_max.add(12));
        System.out.println(stream_k_max.add(1));

    }



}

运行:

5
9
9

进程已结束,退出代码0

十一.求数据流的中位数

/**
 * 求数据流的中位数
 */
public class L295_Stream_Medin {

    /**
     * 实现思路:
     *   比如现在有一个数组: [1,2,3,4,5,6,7,8]
     *   那么它的中位数是 (4+5)/2 = 4.5
     *   如果是:[1,2,3,4,5,6,7,8,9]
     *   那么中位数是 5
     *   一般情况下,每次都先排序,然后找到中位数,这样效率不高,
     *
     *   堆实现:
     *    将数组元素平均分为两份,左边和右边,然后两边分别建堆
     *    left 建立 MaxHeap, right 建立 MinHeap
     *    左边的堆顶是左边最大的,右边的堆顶是右边最小的,
     *    这样,相加除以 2 就可以得到,
     *    如果是奇数,只需要取左边的堆顶元素
     *
     *    向数组中添加元素时:
     *    1.如果两边元素个数一样,向左边添加元素,
     *    2.如果两边个数不一样(左边比右边多一),向右边添加元素
     *     注意:添加元素是有技巧的:
     *      -》向左边添加元素时,先向右边添加元素,然后挤出右边最小的一个元素添加到左边
     *      -》向右边添加元素时,先向左边添加元素,然后挤出左边最大的一个元素添加到右边
     */


    private MaxHeap leftMaxHeap = new MaxHeap(10);

    private MinHeap rightMinHeap = new MinHeap(10);


    public void add(int num){
        //如果左右两边个数相等
        if(leftMaxHeap.size == rightMinHeap.size){
            /**
             * 添加到左边去,但是要先向右添加,再挤出一个最小的到左边
             */
            rightMinHeap.offer(num);
            leftMaxHeap.offer(rightMinHeap.poll());
        }else {
            //左边比右边多一个,同理,先向左添加,然后挤出一个最大的到右边
            leftMaxHeap.offer(num);
            rightMinHeap.offer(leftMaxHeap.poll());
        }

    }

    /**
     * 返回中位数
     * @return
     */
    public double getMedNum(){
        //如果两边个数一样,返回二者堆顶元素平均值
        if(leftMaxHeap.size == rightMinHeap.size){
            return (leftMaxHeap.peek() + rightMinHeap.peek()) / 2.0;
        }else{
            //返回左边元素
            return leftMaxHeap.peek();
        }
    }


    public static void main(String[] args) {

        L295_Stream_Medin stream_medin = new L295_Stream_Medin();

        stream_medin.add(1);
        stream_medin.add(2);
        stream_medin.add(3);
        stream_medin.add(4);
        stream_medin.add(5);
        stream_medin.add(6);
        stream_medin.add(7);
        stream_medin.add(8);
        stream_medin.add(9);

        System.out.println(stream_medin.getMedNum());


    }


}

运行:

5.0

进程已结束,退出代码0
11-12 15:43