c++深入浅出讲解堆排序和堆

本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

目录 一.集合框架的概述 二.集合框架(Java集合可分为Collection 和 Map 两种体系) 三.Collection接口中的方法的使用 四.集合元素的遍历操作 A. 使用(迭代器)Iterator接口 B. jdk5.0新增foreach循环,用于遍历集合.数组 五.Collection子接口之一:List接口 List接口方法 ArrayList的源码分析: JDK 7情况下: JDK 8中ArrayList的变化: LinkedList的源码分析: Vector的源码分析: 六.

目录 一.堆排序 1.什么是堆排序 2.堆排序思想 3.代码实现 二.时间复杂度分析 1.初始化建堆 2.排序重建堆 3.总结 一.堆排序 1.什么是堆排序 (1)堆排序:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. (2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

目录 1.定义字符串 2.字符串的存储 3.String中常用的方法 3.1字符串的比较 3.2查找字符串 3.3转换字符串 4.StringBuilder和StringBuffer 5.常量池 1.定义字符串 字符串常见的构造方式如下: String s1 = "with"; String s2 = new String("with"); char[] array = {'w','i','t','h'}; String s3 = new String(array)

目录 1.this指针的引出 2.this指针的特性 3.练习一下 本篇文章我们将一起讨论在有趣的知识点--隐藏的this指针.本篇我们要使用到之前我们所学习到的C++类与对象,如果有各位小伙伴还不曾了解类与对象的简单思想,可以访问上篇: 在之后的学习中,我们将认识一个新的类:日期类Date.正如我们所想的那样,传入一个日期,我们可以输出我们所输入的日期. 1.this指针的引出 那我们首先来看一下,这段代码会输出什么结果呢? class Date { public: void Display(

目录 写在前面 内存四区 程序运行前 代码区 全局区 程序运行后 栈区 堆区 new关键字 new的基本语法 利用new开辟数组 写在前面 从本文开始我就要日常更新C++入门博文啦,从核心编程开始,之前的一些基础我就不再从零整理了,只有函数传参.结构体.指针.数组等稍微难理解的知识在之前的博文写的比较全面:因为竞争确实很大,其他人总结的也很好,要看更详细的基础就看本站的技能树,非常全面:我写博客的初衷一是可以记录自己的学习,加以巩固:二是给更多的人更容易的讲解来快速入门C++,C/C++永不过时

目录 一.枚举类的使用 二.如何定义枚举类 背景:类的对象只有有限个,确定的.举例如下: > 星期: Monday (星期一).-.. Sunday (星期天) > 性别: Man (男). Woman (女) > 季节: Spring (春节).--.. Winter (冬天) > 支付方式: Cash (现金). WeChatPay (微信). Alipay (支付宝) BankCard (银 行卡). CreditCard (信用卡) > 就职状态: Busy . Fr

目录 一.Map接口继承树 二.Map接口中的常用方法 三.源码分析 1. HashMap的底层实现原理? 2.LinkedHashMap的底层实现原理(了解) 四.Collections工具类 一.Map接口继承树 Map:双列数据,存储key-value对的数据 ---类似于高中的函数:y = f(x) A.HashMap:作为Map的主要实现类:线程不安全的,效率高:存储null的key和value a.LinkedHashMap:保证在遍历map元素时,可以按照添加的顺序实现遍历. 原因

目录 一.利用指针倒序字符串 二.题目实例 三.总结 一.利用指针倒序字符串 void _reversal(char* left, char* right) { while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } 通过上述代码不难看出,left与right分别代表一个字符数组的首端和尾端,通过中间变量 tmp进行首尾交换,left++中的left是char*类型,同

目录 一. 概念: 1. 使用前: 2. 使用后: 二. 理解控制反转(Ioc): 三. IoC的应用方法 一. 概念: 依赖注入(Dependency Injection,DI)与控制反转(IoC)的含义相同,只不过是从两个角度描述的同一个概念.对于一个Spring初学者来说,这两种称呼都很难理解,我们通过简单的语言来描述这两个概念. 使用对比: 1. 使用前: 当某个Java对象(调用者)需要调用另一个Java对象(被调用者,就是被依赖对象)时,在传统模式下,调用者通常会采用"new被调用者