精华内容
下载资源
问答
  • 数组实现的大根堆

    2019-06-18 10:21:32
    大根堆 根节点是所有节点中数值最大的节点 父节点的值总比子节点大 基本操作 Insert 向堆中插入一个值 Update 更新 Heapify 堆化 RemoveTop 删除堆顶元素 GetTop 获得堆顶元素 辅助操作 获得父节点 获得左孩子 ...

    • 一种树状的数据结构

    大根堆

    • 根节点是所有节点中数值最大的节点
    • 父节点的值总比子节点大
    • 基本操作
      • Insert 向堆中插入一个值
      • Update 更新
      • Heapify 堆化
      • RemoveTop 删除堆顶元素
      • GetTop 获得堆顶元素
    • 辅助操作
      • 获得父节点
      • 获得左孩子
      • 获得右孩子
      • 获得当前容量
      • 判断一个节点是否是叶子节点
      • 交换2个节点的位置

    数组大根堆

    • 用数组实现的大根堆
    • 作用
      • 堆排序
      • 求最大值
      • 求第n大的值
    • 基本操作
      • Insert 向堆中插入一个值
      • Update 从指定的节点开始把较大的值和父节点交换直到处理到根节点
      • Heapify 从指定的节点开始把较小的节点和子节点中较大的那个交换直到处理到叶子节点
      • RemoveTop 删除堆顶元素
        • 把堆尾部的元素换到堆顶,堆大小-1
        • 从堆顶开始执行堆化
      • GetTop 获得堆顶元素
    • 辅助操作
      • 获得父节点
        • 父节点和子节点的关系
          • leftChildIndex = parentIndex * 2 + 1
          • rightChildIndex = parentIndex * 2 + 2
          • parentIndex = (childIndex - 1) / 2
      • 获得左孩子
      • 获得右孩子
      • 获得当前容量
      • 判断一个节点是否是叶子节点
        • 如果一个节点的孩子index超过当前容量说明这个节点没有子节点,故为叶子节点
      • 交换2个节点的位置
      • 获得最大容量
      • 根据index判断一个节点是否在堆中
    • 实现代码
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace DataStructure
    {
    
      public class ArrayMaxHeap
      {
        int[] array;
        int size;
        int maxSize;
    
        public void Build(int maxSize)
        {
          array = new int[maxSize];
          this.maxSize = maxSize;
          size = 0;
        }
    
        public int GetSize()
        {
          return size;
        }
    
        public int GetMaxSize()
        {
          return maxSize;
        }
    
        //尾部追加再更新
        public void Insert(int value)
        {
          if (size == maxSize)
          {
            throw new Exception("size must <= max size");
          }
          array[size] = value;
          size++;
          Update(size - 1);
        }
    
        //把大的值往堆顶放
        //把一个大的值从下面换到父节点,直到堆顶
        void Update(int index)
        {
          if (index == 0) return;
          if (index < 0) throw new ArgumentException("index must >= 0");
          if (array[index] > array[ParentIndex(index)])
          {
            Swape(index, ParentIndex(index));
            Update(ParentIndex(index));
          }
        }
    
        public int LeftChildIndex(int index)
        {
          return index * 2 + 1;
        }
    
        public int RightChildIndex(int index)
        {
          return index * 2 + 2;
        }
    
        public int ParentIndex(int index)
        {
          return (index - 1) / 2;
        }
    
        public bool IsLeaf(int index)
        {
          return !IsInHeap(LeftChildIndex(index));
        }
    
        public bool IsInHeap(int index)
        {
          return 0 <= index && index < size;
        }
    
        private void Swape(int index1, int index2)
        {
          var temp = array[index1];
          array[index1] = array[index2];
          array[index2] = temp;
        }
    
        public int GetTop()
        {
          return array[0];
        }
    
        void Heapify(int index)
        {
          if (IsLeaf(index))
          {
            return;
          }
          //找到左边和右边最大的那个子节点,如果子节点更大,交换,对子节点执行堆化,把小的值往堆底放
          //左子节点更大
          if (array[LeftChildIndex(index)] > array[RightChildIndex(index)])
          {
            if (array[index] < array[LeftChildIndex(index)])
            {
              Swape(index, LeftChildIndex(index));
              Heapify(LeftChildIndex(index));
            }
          }
          //右孩子更大,比较右孩子
          else if (array[index] < array[RightChildIndex(index)])
          {
            Swape(index, RightChildIndex(index));
            Heapify(RightChildIndex(index));
          }
    
        }
    
        //取出堆顶,把尾部放到堆顶,执行堆化
        public int RemoveTop()
        {
          if (size == 0) throw new Exception("no element in heap");
          var top = array[0];
          array[0] = array[size - 1];
          size--;
          Heapify(0);
          return top;
        }
    
        public static void Test()
            {
                var array = new int[] { 2, 4, 6, 7, 8, 3, 2, 5 };
                var solution = new ArrayMaxHeap();
                solution.Build(array.Length);
                foreach (var num in array)
                {
                    solution.Insert(num);
                    BaseSolution.print(solution.GetTop());
                    BaseSolution.print(',');
                }
                BaseSolution.println();
                while (solution.GetSize() > 0)
                {
                    BaseSolution.print(solution.RemoveTop());
                    BaseSolution.print(',');
                }
            }
    
      }
    
    }
    
    展开全文
  • 因为插入一个元素时,列表已经是一个大根堆,所以当出现父元素大于自己时,就没有必要继续,因为父元素的父元素值更大。 shift down 删除一个元素时,把该元素和列表的最后一个元素交换。然后列表的长度减一(如果...

    shift up

    • 插入一个元素时,把元素追加到列表的最后,也就是堆的叶子节点上。然后执行shifup操作,对新元素进行从下往上的调整。
    • 判断当前元素是否比父节点更大,如果是,则交换。否则就终止。
    • 因为插入一个元素时,列表已经是一个大根堆,所以当出现父元素大于自己时,就没有必要继续,因为父元素的父元素值更大。

    shift down

    • 删除一个元素时,把该元素和列表的最后一个元素交换。然后列表的长度减一(如果用count计数的话)。剩余的元素进行shiftdown操作。

    • shiftdown,如果两个孩子中存在比自己更大的元素,就和那个孩子交换值。然后这个孩子作为根,继续这个操作。

    • 如下: 插入时执行shiftUp,删除时执行shiftDown

    // 堆排序
    class Heap{
            private List<Integer> data;
    
            public Heap(){
                this.data = new ArrayList<>();
            }
    
            public void insert(int value){
                this.data.add(value);
                this.shiftUp(this.data.size() - 1);
            }
            public int pop(){
                this.swap(0, this.data.size() - 1);
                int res = this.data.remove(this.data.size() - 1);
                this.shiftDown(0);
                return res;
            }
    
            /**
             * 上移,元素加入时执行
             * @param k
             */
            public void shiftUp(int k){
                // 0 元素没有父元素
                // 当出现k比父元素小的时候,就没有必要继续下去,因为,父元素的父元素一定是更大的数
                while(k >= 1 && data.get(k) > data.get((k - 1) / 2)){
                    swap(k, (k - 1) / 2);
                    k = (k - 1) / 2;
                }
            }
    
            /**
             * 下移,调整堆时执行
             * @param k
             */
            public void shiftDown(int k){
                // 省略了对左孩子的判断
                while(2 * k + 1 < data.size()){
                    int child =  2 * k + 1;
                    if(child + 1 < this.data.size() && this.data.get(child) < this.data.get(child + 1)){
                        child += 1;
                    }
                    if(this.data.get(child) > this.data.get(k)){
                        this.swap(k, child);
                    }
                    k = child;
                }
    
            }
    
            public void swap(int left, int right){
                int temp = this.data.get(left);
                this.data.set(left, this.data.get(right));
                this.data.set(right, temp);
            }
        }
        
        // main
            _215_数组中的第k个最大元素.Heap2 heap = handle.new Heap2();
            // 建立堆
            for(int item : list){
                heap.insert(item);
            }
            for(int item : list){
                System.out.print(heap.pop() + " ");
            }
    

    heapify

    • 不需要一个一个的插入元素,可以直接对原数组的所有非叶节点进行heapify,即可构成一个大根堆。
    • ((size - 1) - 1) / 2 表示最大下标减一。当然,用size/2也行,多出的几个元素都是叶子节点,都可以当成是只有一个元素的堆。
            public Heap2(List<Integer> list){
                this.data = new ArrayList<>(list);
                heapify();
            }
            public void heapify(){
                for(int i = (data.size() - 1 - 1) / 2; i >= 0; --i){
                    shiftDown(i);
                }
            }
    

    就地排序

    • 这里的nums数组的数据从0开始拍,这样的话,按照如下方式计算父子节点
      • 左孩子: index * 2 + 1
      • 右孩子: index * 2 + 2
      • 父节点: (index - 1) / 2 或者 (length -1 -1)/2。有的算法直接用 (length / 2)也不会有错,因为最右边的叶子节点都可以看成是单个的大根堆。
    class Heap {
            public void heapSort(int [] nums){
                // 从第一个非叶节点开始,执行shiftdown操作
                int size = nums.length;
    
                // 建立一个堆
                // 很多携程(size-1)/2 或者 size/2都行
                for( int i = (size -1 - 1)/2; i >= 0; --i){
                    shiftDown(nums, i, size);
                }
                // 从堆中取元素
                for (int i = size - 1; i > 0; i --){
                    swap(nums, 0, i);           // i 元素被放到0位置
                    shiftDown(nums, 0, i);      // 重新堆0位置的元素shiftdown
                }
            }
    
            /**
             * 对第i个元素执行下移操作。大根堆
             * @param nums
             * @param i
             */
            public void shiftDown(int [] nums, int k, int size){
                // 用while 少了一次循环,避免了递归
                while( 2 * k + 1 < size){
                    int child = 2 * k + 1;      // 左孩子
                    if ( child + 1 < size && nums[child+1] > nums[child])
                        child += 1;             // 右孩子
    
                    if (nums[k] < nums[child]){
                        swap(nums, child, k);
                    }
    
                    k = child;                  // 从被交换的孩子开始,继续往下迭代。直到到达叶子节点
                }
            }
    
            public void swap(int[] a, int i, int j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    
    展开全文
  • 大根堆创建于排序

    2019-05-23 17:18:21
    创建大根堆 static void buildBigHeap(int[] array, int last) { //从最大的非叶子节点开始(last - 1 /2),到根节点终止 for (int i = (last -1) / 2; i >= 0; i--) { int k = i; //判断是否超过数组...

    创建大根堆

       static void buildBigHeap(int[] array, int last) {
            //从最大的非叶子节点开始(last - 1 /2),到根节点终止
            for (int i = (last -1) / 2; i >= 0; i--) {
                int k = i;
                //判断是否超过数组界限,第一轮比较完,该子节点作为父节点时是否为最大值情况
                while ((2 * k) + 1 <= last){
                    //记录最大值的下标
                    int bigIndex = 2*k+1;
                    //判断是否右子节点,如果相等无右子节点。小于则右
                    if(bigIndex < last){
                        //判断左右子节点的大小
                        if(array[bigIndex] < array[bigIndex + 1]){
                            bigIndex++;
                        }
                    }
                    //最大子节点和父节点比较
                    if(array[k] < array[bigIndex]){
                        MyUtil.swap(array,k,bigIndex);
                        System.out.println(Arrays.toString(array)+"有交换"+ "\t" +"父节点 = " + k +  "\t" + "最大子节点 = " + bigIndex);
                        k = bigIndex;
                    }
                    else {
                        System.out.println(Arrays.toString(array)+"无交换");
                        break;
                    }
                }
            }
        }
    

    创建大根堆思路

    首先找到最后的父节点 ,从下标0开始所以为int last = (array.length -1 -1 )/2
    所以父节点一共有0 到 last 个
    记录一下当前父节点的下标
    以左子节点来判断是否超过数组界限
    找出左右子节点的最大值
    然后和父节点的值进行比较 交换位置

    大根堆排序code

    public static void  headSort(int[] nums){
        System.out.println("原始数组 =" + Arrays.toString(nums));
        System.out.println("-----------------------------------");
        for(int i = nums.length - 1 ; i > 0; i--){
            buildBigHeap(nums, i);
            MyUtil.swap(nums, i , 0);
        }
    }
    

    思路

    每次都将前面的值放到最后
    因为每次放完后在进行大根堆重组的时候,重组数组大小减1,所以 9 8 7 6 5 4 3 2 1 的顺序排成从小到大

    测试code

    public static void main(String[] args){
        int[] array = MyUtil.createArray();
        int[] arrays = new int[array.length];
        System.arraycopy(array,0,arrays,0,array.length);
        //系统排序
        Arrays.sort(arrays);
        //堆排序
        HeapSort.headSort(array);
        boolean compare = MyUtil.compare(array,arrays);
        System.out.println(compare);
    }
    
    展开全文
  • 问题描述: 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于...首先向大根堆里面加入元素,如果加入元素不满足条件,那么再进行下一步操作,其中条件是:1)大根堆

    问题描述:
    如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
    样例

    • 输入:1, 2, 3, 4
    • 输出:1,1.5,2,2.5
      解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。

    使用大根堆维护序列的前半部分,使用小根堆维护序列的后半部分。序列是指的从小到大排列。首先向大根堆里面加入元素,如果加入元素不满足条件,那么再进行下一步操作,其中条件是:1)大根堆里面的元素最多只能比小根堆的元素多1个,如果多两个的话,就需要将大根堆的元素弹出来放到小根堆里面去,2)如果大根堆里面的堆顶元素大于小根堆里面的堆顶元素,那么这样的序列不是有序的,则需要交换这两个元素使得大的部分在小根堆里,小的部分在大根堆里。

    class Solution {
    public:
        priority_queue<int> max_heap;
        priority_queue<int,vector<int>,greater<int>> min_heap;
        void insert(int num){
            max_heap.push(num);
            if(min_heap.size()&&max_heap.top()>min_heap.top())
            {
                auto maxv=max_heap.top(),minv=min_heap.top();
                max_heap.pop(),min_heap.pop();
                max_heap.push(minv),min_heap.push(maxv);
            }
            if(max_heap.size()>min_heap.size()+1)
            {
                min_heap.push(max_heap.top());
                max_heap.pop();
            }
        }
    
        double getMedian(){
            if(max_heap.size() + min_heap.size() & 1) return max_heap.top();
            return (max_heap.top()+min_heap.top())/2.0;
        }
    };
    
    展开全文
  • 下面对Java中的栈、队列、小根堆和大根堆做一个简单的介绍。 它们都有共用的collections接口中定义的常见函数isEmpty(),可以判断该数据结构中是否还有元素。 栈 Java中有Stack类,但现在已经过时了,不推荐使用。一...
  • **题目描述** 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间...利用两个堆,一个大根堆一个小根堆。然后插入的时候通过两者的size和顶部的数字进行判断。...
  • 8 25 70 8 25 82 8 38 52 8 38 58 60 Min Heap Sample Input 3: 8 10 28 15 12 34 9 8 56 Sample Output 3: 10 15 8 10 15 9 10 28 34 10 28 12 56 Not Heap 题目大意 判断一棵完全二叉树为大根堆、小根堆,或者不是...
  • 满二叉树 完全二叉树的定义 满二叉树就是每一层节点个数都是满的二叉树。第n层节点个数 = pow(2,n - 1...关于完全二叉树的几个面试题目一:判断是不是完全二叉树 思路:层次遍历:当前节点左子树不空放入queu...
  • 一、巧用数组下标数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些字母作为下标,在遍历的...
  • 1. 巧用取余有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:for (int i = 0; i < N; ...
  • 判断

    千次阅读 2018-04-26 17:58:37
    = k[2*i+1]大根堆:k[i] &gt;= k[2*i] 且 k[i] &gt;= k[2*i+1]#include&lt;iostream&gt;(小根堆判断)using namespace std;int main(){ int n; cin&gt;&gt;n; int a[n]; f...
  • 3(3,3) 由广义表构成的二叉树,是属于大根堆还是小根堆呢? 求大侠解答一下,我是小白
  • 下列各序列中不是堆的是() ...参考答案是C,说A和D都是大根堆,但觉得答案有问题,按照“大根堆大于等于左右子节点的值”,A中的36小于47,大于30;同样地,D中的12小于24和36,这有问题吧?求大侠指教,谢谢
  • 堆分成大顶堆和小顶堆,大根堆要求根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。小顶堆相反。 —————————————————————————————— 一堆的建立(以小...
  • 题目传送门 这题.....看个标题和数据基本就能...判断大根堆和小跟堆我是判断了两次,先判断是否是大根堆,在判断是否是小跟堆,判断方法就是遍历每个点,判断每个点是不是都满足堆得性质 #include&lt;iostrea...
  • 排序

    2020-08-09 22:33:53
    建立大根堆的时间复杂度是log(N),与大根堆的高度有关。 小根堆: 任何一棵子树的最小值都是头部 数组如何建立大根堆: 从0开始遍历数组,0-i位置之间形成大根堆判断i位置和(i-1)/2,即父节点的大小,假如比父节点...
  • 堆分为大根堆和小根堆,是完全二叉树。前面我已经有二叉树入门的文章了,当时讲解的是二叉查找树,那上面所说的完全二叉树是怎么样的一种二叉树呢??还有满二叉树又是怎么的一种二叉树呢??甚至还有完满二叉树??...
  • 如果根节点最小,称之为小顶堆(或小根堆),如果根节点最大,称之为大顶堆(或大根堆)。 注意:堆的左右孩子没有大小的顺序。 关于堆的判断 这道题目完全可以看成一道堆的模板题,只要构建出小顶堆其他都好说。...
  • 二叉

    2020-02-06 22:02:45
    也就是我们通常说的大根堆和小根堆。而这里的最大和最小是根据题目中的优先级来判断最大最小的,而不是我们所想的大和小。 左图为最大堆,右图为最小堆(他们优先级为数字大小)。同时他没棵子树也是一个最小(大)...
  • 首先,维护一个大根堆和一个小根堆 大根堆维护数列中小的部分,小根堆维护数列中大的部分 然后,每次输入两个数,大的加入小根堆,小的加入大根堆 为什么? 我不知道 还有一个玄学操作: 把两个堆堆顶判断一下,大根...
  • 二叉--优先队列

    2019-02-27 21:26:17
    堆:堆常见的二叉堆,这种数据结构有大根堆和小根堆。对于大根堆来说,每个父节点是大于他的两个孩子节点的。也就是最大值在根节点。小根堆与之相反。如果堆用数组实现的话,如果从0开始计数,那么一个孩子的父节点...
  • 二叉的插入与删除

    2020-02-06 21:23:27
    3.堆一般有俩种形式,大根堆和小根堆,大根堆是堆顶的优先级最大,小根堆就是堆顶的优先级最小 二.堆的操作 一. 插入 堆的插入就是把新的元素放到堆底,然后去判断是否符合这个位置的要求,如果符合就丢在那里了,...
  • 思路上面几位都说得比较清晰了,就是动态维护中位数,然后每次求最小代价,当时我脑袋一热,就想到了对顶堆,就是定义1个小根堆和1个大根堆,每次判断当前的数如果小于大根堆顶,就加入大根堆,否则加入小根...
  • 和优先队列总结

    2020-04-30 16:56:35
    满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆 反之则是小堆,或者小根堆,或者最小堆 向下调整 前提:左右子树必须是一个堆才能调整 过程(以小堆为例) 1.index如果已经是叶子节点,...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 121
精华内容 48
关键字:

判断大根堆