精华内容
下载资源
问答
  • 小根堆排序

    2017-07-24 17:08:00
    小根堆排序,使用数组模拟堆,时间复杂度为O(nlogn) 调整部分的程序比较难理解,有的地方还是不太清楚。 代码如下: #include <iostream> using namespace std; const int N = 100000; int ...

    2017-07-24 17:04:23

    writer:pprp

    参考书目:张新华的《算法竞赛宝典》

    小根堆排序,使用数组模拟堆,时间复杂度为O(nlogn)

    调整部分的程序比较难理解,有的地方还是不太清楚。

    代码如下:

    #include <iostream>
    
    using namespace std;
    
    const int N = 100000;
    
    int a[N+1];
    
    void adjust_down(int i,int m)
    {
        int tmp;
        while(i*2 <= m)
        {
            i *= 2;
            if((i < m)&&(a[i+1]>a[i]))  //通过这个if判断左右哪个更大一点
                i++;
            if(a[i] > a[i/2]) // 如果max(左,右) > 父节点,那么交换
            {
                tmp = a[i];
                a[i] = a[i/2];
                a[i/2] = tmp;
            }
            else    //如果符合最小堆,那么不进行操作
            {
                break;
            }
        }
    }
    
    int main()
    {
    
        int n;
        int i;
    
        cin >> n;
        // 从1开始用
        for(i = 1 ; i <= n ; i++)
        {
            cin >> a[i];
        }
    
        for(i = n/2; i>=1; i--)   // 只需从一半开始调整??
        {
            adjust_down(i,n);      //建立堆
        }
    
        for(i = n; i >= 2; i--)
        {
    //        int tmp = a[i];
    //        a[i] = a[1];
    //        a[1] = tmp;
            a[i] = a[i]^a[1];
            a[1] = a[1]^a[i];
            a[i] = a[i]^a[1];
            adjust_down(1,i-1); //从1开始到i-1开始调整堆
        }
    
        for(i = 1 ; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    
        return 0;
    }

     

    转载于:https://www.cnblogs.com/pprp/p/7229949.html

    展开全文
  • 大根堆/小根堆排序

    2021-01-02 13:14:14
    堆排序之大根堆/小根堆篇堆Min-heapMax-heap堆的存储堆的操作:insert堆的操作:Removemax堆的操作: buildHeap堆排序示例 堆 ** 1>: 完整的二叉树 2>:heap中存储的值是偏序 ** Min-heap 父节点的值小于或等于...

        1>: 完整的二叉树
        2>:heap中存储的值是偏序
    

    Min-heap

    	父节点的值小于或等于子节点的值
    

    Max-heap

    	父节点的值大于或等于子节点的值
    

    Max-Heap
    Min-Heap

    堆的存储

    • 一般都用数组来表是堆,i 节点的父节点下标就为(i-1)/2.
    • 它左右子节点下标分别为 2 * i + 1 和 2 * i + 2;(如 第0个节点左右下标分别为 1 和 2)

    堆的操作:insert

    插入一个元素:新元素被加入到了heap的末尾,然后更新树以恢复堆的次序
    每次插入都是将新数据放在数组的最后,可以发现从这个新数据的父节点到根节点
    必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序的数据中。这就
    类似于将一个数据并入一个有序的区间当中
    

    插入45图1
    插入45 图2插入 45 图3

    插入45 图4

    堆的操作:Removemax

    按定义,堆中每次都删除第0个数据。为了便于重建堆。实际的操作是将最后一个数据
    的值赋给根节点,然后在从根节点开始进行一次从上向下的调整。调整时先在左右子
    节点中找最大的。如果父节点比这个最小的子节点还大说明不需要调整了。反之将
    父节点和它交换后在考虑后面的节点。相当于从根节点将一个数据“下沉”过程
    

    在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    堆的操作: buildHeap

    对于叶子节点,不用调整顺序,根据满二叉树的性质。叶子节点比内部节点的个数多1
    所以 i = n / 2-1 不用从 n 开始
    

    堆排序

    堆构建好后堆中第0个数据是堆中最大的数据。取出这个数据在执行下堆的删除操作。
    这样堆中的第0个数据又是堆中最大的数据。重复步骤直至堆中只有一个数据时。
    就直接取出这个数据。
    

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    堆排序(完整二叉树)最后一个非叶子节点的序号是 n / 2 - 1 的原因
    堆排序是基于完全的二叉树实现的,在将一个数组形成堆的时候。关键之一的是确定最后一个非叶子节点的序号。
    这个序号为 n / 2 - 1 ;n 为数组的长度
    
    可以分为俩种情况考虑:
    	1>堆的最后一个非叶子节点只有左节点
    	2>堆的最后一个非叶子节点有左右节点
    完整二叉树的性质是 如果节点的序号为 i 。 在他左孩子的节点为 2 * i +  1 ; 右孩子为 2 * i + 2
    对于 1 左孩子的序号为 n - 1; n - 1 = 2 * i + 1  则 i = n / 2 -1;   			// 6 - 1 = 5 ;  6 - 1 = 2 * 2 + 1 ; 2 = 6 / 2 - 1  
    对于 2 左孩子的序号为 n - 2; n - 2 = 2 * i + 1  则 i = ( n - 1) / 2 - 1; 		// 7 -2 = 2 * 2 + 1 则 2 = ( 7 - 1) / 2 - 1 ; 
    对于 2 右孩子的序号为 n - 1; n - 1 = 2 * i + 2  则 i = ( n - 1);  				// 7 - 1 ; 7 - 1 = 2 * 2 + 2 则 2 = ( 7 - 1) / 2 - 1 
    
    很显然,当完整二叉树最后一个节点是其父节点左叶子节点时,树的节点数为奇数,当最后一个节点是子节点时。树的节点数为偶数
    根据 Java 语法特性 整数除不尽时向下取整。若为奇数时为( n - 1 )/ 2 - 1  =  n / 2 - 1;
    因此对于 2 最后一个非叶子节点的序号也是 n / 2 -1;
    

    示例

    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<>();
            if (input == null || input.length == 0 || k > input.length || k == 0)
                return list;
            int[] arr = new int[k + 1];//数组下标0的位置作为哨兵,不存储数据
            //初始化数组
            if (k + 1 - 1 >= 0) System.arraycopy(input, 0, arr, 1, k + 1 - 1);
    
            buildMaxHeap(arr, k + 1);//构造大根堆
            for (int i = k; i < input.length; i++) {
                if (input[i] < arr[1]) {
                    arr[1] = input[i];
                    adjustDown(arr, 1, k + 1);//将改变了根节点的二叉树继续调整为大根堆
                }
            }
            for (int i = 1; i < arr.length; i++) {
                list.add(arr[i]);
            }
            return list;
        }
    
        public void buildMaxHeap(int[] arr, int length) {
            if (arr == null || arr.length == 0 || arr.length == 1)
                return;
            for (int i = (length - 1) / 2; i > 0; i--) {
                adjustDown(arr, i, arr.length);
            }
        }
    
        public void adjustDown(int[] arr, int k, int length) {
            arr[0] = arr[k];//哨兵
            for (int i = 2 * k; i <= length; i *= 2) {
                if (i < length - 1 && arr[i] < arr[i + 1])
                    i++;//取k较大的子结点的下标
                if (i > length - 1 || arr[0] >= arr[i])
                    break;
                else {
                    arr[k] = arr[i];
                    k = i; //向下筛选
                }
            }
            arr[k] = arr[0];
        }
    
        public static void main(String[] args) {
            int[] arr = new int[]{4,5,1,6,2,7,3,8};
            int k = 5;
            Solution solution = new Solution();
            ArrayList<Integer> integers = solution.GetLeastNumbers_Solution(arr, k);
            integers.forEach(System.out::println);
    
        }
    }
    
    
    展开全文
  • 小根堆排序

    千次阅读 2007-09-29 11:44:00
    在找工作的过程中,有一家公司...用JAVA实现了小根堆排序算法。与大家分享一下。package src;import java.util.Arrays;public class HeapSort { public static void main(String[] args) { int[] arry_int={49,38,6

    在找工作的过程中,有一家公司面试,通过小根堆实现数组排序。当时,没有写出来,下来后自己研究了下。用JAVA实现了小根堆排序算法。与大家分享一下。

    package src;
    import java.util.Arrays;
    public class HeapSort {
     
     public static void main(String[] args)
     {
      int[] arry_int={49,38,65,97,76,13,27,55};
      //int[] arry_int={13, 38, 27, 55, 76, 65, 49, 97};
      HeapSort hsort=new HeapSort();
      hsort.HeapSorting(arry_int);
      //System.out.println(Arrays.toString(arry_int));
     }
        //调整无序序列为大根堆 s 为数组的起始下标,m为终止下标
     public void HeapAdjust(int[] arr, int s,int m)
     {
      int temp=arr[s];
      for(int j=2*s+1;j<m;j=j*2+1)
      {
       if(j+1<m && arr[j]>arr[j+1]) ++j;
       if(temp<arr[j])break;
       arr[s]=arr[j];
       s=j;
       arr[s]=temp;
         
      }
     }
     //根据大根堆,对堆排序
     public void HeapSorting(int[] arr)
     {
            //把顺序表构建成为一个大根堆
      
      
      for(int i=(arr.length/2-1);i>=0;--i)
      {
       
       HeapAdjust(arr,i,arr.length);
      }
      
      for(int j=arr.length-1;j>0;--j)
      {
       System.out.println("堆顶元素 arrr[0]="+arr[0]);
       System.out.println("arr["+j+"]="+arr[j]);
       System.out.println("将当前锥顶元素与第"+j+"个元素互换");
       int temp=arr[0];
       arr[0]=arr[j];
       arr[j]=temp;
       
       HeapAdjust(arr,0,j);
       System.out.println(Arrays.toString(arr));
      }
      
      
     }
    }
     

    展开全文
  • 小根堆 排序 学习

    千次阅读 2013-04-02 17:14:14
    先了解一下,如何创建一个小根堆,如何插入一个元素 有配图,看完了这篇,应该就理解了 小根堆 总结 topN算法中,的场景 应该是一个已经排序完毕的,小根堆,如果当前比较的元素,比小根堆大,那么,替换掉,...

    先了解一下,如何创建一个小根堆,如何插入一个元素

    有配图,看完了这篇,应该就理解了

    小根堆 总结

    topN算法中,的场景

    应该是一个已经排序完毕的,小根堆,如果当前比较的元素,比小根堆大,那么,替换掉,堆顶元素,然后,重新排序。

    堆排序

    (1)如何由一个无需数列建成一个堆?

    (2)如何在输出堆顶元素之后,调整剩余元素成为一个新的堆。


    巴拉巴拉……

    我们把这个自堆顶到叶子的调整过程,有一个专门的术语叫“筛选”。(参看数据结构292页)

    最后还是看这本书,看懂的,严蔚敏的那本数据结构c语言版,教材

    展开全文
  • [十套数据结构试题及答案] 小根堆排序图解 数据结构试卷一 1 数据结构试卷二 4 数据结构试卷三 6 数据结构试卷四 8 数据结构试卷五 11 数据结构试卷六 14 数据结构试卷七 16 数据结构试卷八 18 数据结构试卷九 20 ...
  • //利用小根堆排序 cout ; for (int j = sizeof(array) / sizeof(array[0]) - 1; j > 0; j--) { int temp = array[j]; array[j] = array[0]; array[0] = temp; //for (int i = j / 2 - 1; i >= 0; i--) ...
  • link下大根堆小根堆排序后的线性搜索是怎么做的?如何才能做到高效率?
  • JAVA实现小根堆排序

    2019-08-27 14:22:28
    //必须要产生交换 不然后面序列满足小根堆或者大根堆的条件 不再发生变化 heapAdjust(arr,0,i-1); } } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
  • Java 小根堆排序

    2014-12-27 19:22:11
     //建立小根堆  public void buildMaxHeap(List data, int lastIndex) {  //从lastIndex节点的父节点开始舰堆  for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  //保存正在判断的节点 ...
  • 小根堆:任何子树的最小值都是子树的根节点。 用处:比如实时求所输入数据的中位数。 大根堆的建立:有任何一个子树变成大根堆。复杂度=log1+ log2+… +logN=O(N) import java . util . Arrays ; public ...
  • 堆排序小根堆

    千次阅读 2014-12-22 16:27:17
    小根堆排序
  • 大根堆排序算法实现小根堆排序算法1.交换操作2.对结点进行调整为小根堆3.建立小根堆4.大根堆排序算法实现项目完整代码运行效果图 大根堆排序算法 1.交换操作 //交换实现 void swap(int &a, int &b) { int ...
  • 小根堆,大根堆,堆排序 下面用c++模板实现小根堆,大根堆,堆排序功能, 可以适用不同类型的数据,可以直接使用 //file:heap.h #ifndef _AGILE_HEAP_H_ #define _AGILE_HEAP_H_ #include #include typedef ...
  • 堆与数组的关系 堆是一种逻辑结构(形象的表示数据的存储格式),数组则是数据的实际存储结构(对应数据的存储地址),堆中的节点与左右子节点在存储数组中的位置关系... /// 堆排序算法 /// </summary> st
  • 堆排序小根堆实现

    2020-12-11 17:42:56
    我把堆排序算法拿出来给大家看看,这个算法在我的学生成绩管理系统里也有体现,注意:数组的0下标是不存任何数据的,因为是完全二叉树,节点的坐标是1才有利于进行计算。 #include<iostream> using ...
  • 堆排序-以小根堆为例

    2020-09-29 10:57:49
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录前言一、什么是堆二、堆排序过程1.创建堆2.堆排序总结前言一、pandas是什么?二、使用步骤1....下面将以小根堆(就是下层比
  • 堆排序小根堆

    千次阅读 2018-07-26 20:16:37
    一、  1.概念:它是一种完全二叉树(即前n-1层是满...的目的:排序  3.的创建:创建一棵完全二叉树  4.存储方式:链式存储,按层存储  5.算法:建立结构体,声明结点类型  typedef struct node{  ...
  • 堆排序—大根堆,小根堆

    千次阅读 2017-02-04 15:27:30
    1.小根堆 若根节点存在左子女则根节点的值小于左子女的值;若根节点存在右子女则根节点的值小于右子女的值。 2.大根堆 若根节点存在左子女则根节点的值大于左子女的值;若根节点存在右子女则根节点的值大于右子女...
  • 小根堆:根节点value不大于子节点的value,满足这条性质的二叉树即为小根堆。 从大根堆的定义可知:在大根堆里要得到最大值只需o(1)的时间。所以很明显,大根堆可以求最大值和维护前k小的数。注意是前k小的数,不是...
  • 堆排序算法平均时间复杂度近似为O(nlog2(n)),2为下标,与快速排序、希尔排序一样为不稳定算法。 实现思路 首先我们得到一串整型序列[9 4 2 6 1 8 3 5 7] 实现代码 //这里的排序用的是大根堆 #include <bits/stdc...
  • 小根堆实现的堆排序

    2011-08-17 14:56:00
    输入: 第一行输入一个整数N,代表要排序元素的个数 以下N行输入N个要排序的元素 输出: 从小到大依次输出各元素 #include<...void heap(int s, int n){ //调整堆,使其始终为小根堆 int i...
  • C++ 堆排序建立小根堆

    2019-05-10 23:20:24
    #include <iostream> #include <vector> #include <algorithm> using namespace std; class Heap{ public: vector<int> heap_vector; int Length = 10;... heap_vector...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,247
精华内容 1,298
关键字:

小根堆排序