1. IT分享知识网首页
  2. 开发语言
  3. java

Java数据结构之堆

老牧童 • • java • 阅读 164

Java数据结构之堆堆的概念堆逻辑上是一棵完全二叉树堆物理上是保存在数组中满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆反之，则是小堆，或者小根堆，或者最小堆堆的基本作用是快速找集合中的最值二叉树的顺序存储使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。这种方式的用法就是堆的表示。顺序存储中的双亲与孩子的下标关系已知双亲的下标：左孩子下标=2*parent+1;右孩子下标=2*parent

大家好，欢迎来到IT知识分享网。

堆的概念

  1. 堆逻辑上是一棵完全二叉树
  2. 堆物理上是保存在数组中
  3. 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆
  4. 反之，则是小堆，或者小根堆，或者最小堆
  5. 堆的基本作用是快速找集合中的最值

二叉树的顺序存储

使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的用法就是堆的表示。

顺序存储中的双亲与孩子的下标关系

已知双亲的下标：

  1. 左孩子下标 = 2*parent+1;
  2. 右孩子下标 = 2*parent+1;

已知孩子下标：

  1. 双亲下标 = (child – 1) / 2;

建堆与向上调整
在这里插入图片描述
在这里插入图片描述
将二叉树调整成大根堆

public class Heap { 
   
    // 定义数组和数组的长度
    public int[] elem;
    public int usedSize;

    public Heap(){ 
   
        this.elem = new int[10];
    }
    /** * 将一棵树调整大堆的思路 * 1.每棵子树都应该变成大堆 * 2.最主要的逻辑：从最后一棵子树开始进行调整（从4下标开始） * 3.怎么调整 * 4.定义子树父亲节点p 孩子节点c * 5.在父亲节点的左右两边找到左右孩子的最大值 * 6.让左右孩子的c 最大值 跟父亲节点进行交换 * 7.注意：让p走到c 让c继续走 发现c超出下标 那就证明这棵子树交换完了 * 8.然后再调整上一个子树 【其实是换下标 换p换c 继续调整】 树的思想 下标的操作 * * */
    public void createHeap(int[] array){ 
   

        for (int i = 0; i < array.length; i++) { 
   
            // 把数组的值拷贝给 elem
            this.elem[i] = array[i];
            this.usedSize++;
        }

        // parent 就代表每棵子树的根节点
        // 如何拿到最后 最后一个节点的下标: array.length-1
        // 最后一个节点的父节点: (array.length-1-1)/2
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) { 
   
            // 注意：第2个参数 每次调整的结束位置应该是：不超过数组的最大值，下标不取等于就行
            // this.usedSize
            adjustDown(parent,this.usedSize);
        }
    }
	// root:每棵树的根值 len:数组长度
    private void adjustDown(int root, int len) { 
   
        int parent = root;
        int child = 2*parent+1;

        // 在调整的过程中 child要小于len 防止数组越界
        // 只要能进循环 就代表至少有左孩子
        while (child < len){ 
   
            // 找到左右孩子的最大值

            // 1.前提是你得有右孩子
            // 先判断是否有有孩子，并且判断左右孩子哪个大，并保证child是两个孩子中值最大的那一个
            if(child+1 < len && this.elem[child] < this.elem[child+1]){ 
   
                // 保证child是两个孩子中值最大的那一个
                child++;
            }
            // 保证，child下标的数据 一定是左右孩子的最大值的下标
            if(this.elem[child] > this.elem[parent]){ 
   
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
				// 先移动parent
                parent = child;
                // 再移动child
                child = 2*parent+1;
            }else { 
   
                // 当调整的过程中，孩子节点没有父亲节点的值大，那么此时说明这棵树已经是大根堆了
                break;
            }
        }
    }
}

时间复杂度
要计算最坏的时间复杂度，实际上就是一棵满二叉树，这样每棵树都会进行调整

  1. 每一层有多少个节点
  2. 时间复杂度与节点的高度h和每层节点的个数有关

T(n) = 2^0 * (h-1)+2^1 *(h-2)+…+2^(h-2) * 1

2*T(n) = 2^1 *(h-1)+ 2^2 * (h-2)+2^3 *(h-3)+…+2^(h-1) * 1

错位相减
T(n) = 2^h – 1 – h

假设共有n个节点 n = 2^h – 1
2^h = n+1 h = log2(n+1)

T(n) = n – log2(n+1)
当n慢慢变大的时候，整个表达式的结果就趋近于n

堆的应用-优先级队列

优先级队列数据结构：应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。

内部原理：优先级队列的实现方式有多种，但最常见的是使用堆来构建

入队列

  1. 首先按尾插方式放入数组
  2. 比较其和双亲的值的大小，如果双亲的值大，则满足堆的性质，插入结束
  3. 否则，交换其和双亲位置的值，重新进行2,3步骤
  4. 直接根节点
	// child是新插入数据的下标
	public void adjustUp(int child){ 
   
        int parent = (child-1)/2;
        while (child > 0){ 
   
            if(this.elem[child]>this.elem[parent]){ 
   
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else { 
   
                break;
            }
        }
    }
    public void push(int val){ 
   
        if(ifFull()){ 
   
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        adjustUp(this.usedSize-1);
    }

    private boolean ifFull() { 
   
        if(this.elem.length == this.usedSize){ 
   
            return true;
        }else { 
   
            return false;
        }
    }

出队列（出堆顶 优先级最高的）

为了防止破坏堆的结构，删除时并不是将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向下调整方式重新调整成堆。

	public void pop(){ 
   
        if(isEmpty()){ 
   
            return;
        }
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
        adjustDown(0,this.usedSize);

    }

    public boolean isEmpty(){ 
   
        return this.usedSize==0;
    }

返回队首元素

	public int peek(){ 
   
        if(isEmpty()){ 
   
            // return -1;
            throw new RuntimeException();
        }
        return this.elem[0];
    }

堆的其他应用-TopK问题

问题：给100万个数据排序，取前10个最大的

  1. 基本思路：直接Array.sort();
  2. 建立一个堆，这个堆是大堆，取前10个。缺点是堆太大了，堆大小也是100万。
  3. 建立一个大小为K的小堆。将当前数组的前K个建立为小堆；遍历剩下的元素，依次和堆顶元素比较，如果当前i下标元素比堆顶元素大，就把i下标入队。

相反，如果找前K个最小的，建堆就是大堆。

从数组中找最小的K个数据

    public static void topK(int[] array,int k){ 
   
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() { 
   
            @Override
            public int compare(Integer o1, Integer o2) { 
   
                return o2-o1;
            }
        });
        // 建立大堆
        for (int i = 0; i < array.length; i++) { 
   
            if(maxHeap.size() < k){ 
   
            	// 优先级队列会自动调整为大堆
                maxHeap.offer(array[i]);
            }else { 
   
                int top = maxHeap.peek();
                if (top > array[i]){ 
   
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        System.out.println(maxHeap);
    }

堆的其他应用-堆排序

从小到大排序 建立大堆

	public void heapSort(){ 
   
        int end = this.usedSize-1;
        while (end>0){ 
   
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] =tmp;
            adjustDown(0,end);
            end--;
        }
    }

从大到小排序 建立小堆

LeetCode373. 查找和最小的 K 对数字

class Solution { 
   
    public List<List<Integer>> kSmallestPairs(int[] nums1,int[] nums2,int k){ 
   

        PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() { 
   
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) { 
   
                /** * o2 和 o1 存的是List的引用 * */
                 // o2 -o1 的变形
                return (o2.get(0)+o2.get(1)) - (o1.get(0)+o1.get(1));
            }
        });
        for (int i = 0; i < nums1.length; i++) { 
   
            for (int j = 0; j < nums2.length; j++) { 
   
                if(maxHeap.size()<k){ 
   
                    List<Integer> pair = new ArrayList<>();
                    pair.add(nums1[i]);
                    pair.add(nums2[j]);
                    maxHeap.offer(pair);
                }else { 
   
                    List<Integer> top = maxHeap.peek();
                    // 如果当前元素 比 堆顶小 就弹出堆顶 然后将小的数据放入堆
                    int topValue = top.get(0)+top.get(1);

                    if(topValue > nums1[i]+nums2[j]){ 
   
                        maxHeap.poll();
                        List<Integer> pair = new ArrayList<>();
                        pair.add(nums1[i]);
                        pair.add(nums2[j]);
                        maxHeap.offer(pair);
                    }
                }
            }
        }

        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) { 
   
            // 将堆弹出的元素放到ret中
            ret.add(maxHeap.poll());
        }
        return ret;
    }
}

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/15563.html

赞 (0)
老牧童老牧童
0
上一篇 2024-02-16 13:26
下一篇 2024-02-16 20:00

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信