算法（4）数据结构：堆
1.0 问题描述
实现数据结构：堆。
2.0 问题分析
- 堆一般使用数组来表示，其中某个节点下标i的两个子节点的下标为 2i+1 和 2i+2。堆是一棵完全二叉树。
- 堆有3种基本操作：创建，插入，删除。
- 这3种操作都需要通过“调整堆”的方式来实现。调整堆是指，对堆中的某个节点，若它的值和它所有子节点相比，不是最大/最小，那么就需要将最大/最小的元素和当前节点交换，这种操作成为“调整堆”。
- 创建可以用插入来实现（复杂度O(nlogn)），也可以使用数组直接转换成堆（复杂度O(n)）。
- 假设数组长度为n，那么这个数组转成堆，需要从第一个有子节点的节点((n - 1)/2或(n - 2)/2开始，倒序“调整堆”，直到下标为0。
- 插入操作可以先将数据插入到数组尾部，然后依次调整该数据的父节点，父节点的父节点…直到根节点。
- 删除操作可以先将数组首尾节点互换，然后删除最后面的元素，最后再调整根节点即可。
3.0 代码实现
3.1使用swift实现
/** 堆类型* small 小根堆* big 大根堆*/
enum HeapType {case small, big
}/** 堆*/
class Heap<T: Comparable> {private var _arr: [T];private var _type: HeapType;/** 使用数组创建堆* @param {[T]} - arr 创建堆的数组* @param {HeapType} - type 堆类型*/init(arr: [T], type: HeapType = .big) {self._arr = arr;self._type = type;self._create();}/** 调整堆：调整以idx为顶的3元素子堆，若顶部元素不是最大/最小，则调整为最大/最小* @param {Int} - idx 表示调整以idx为顶的3元素子堆* @return {Bool} - 调整成功返回true，无需调整返回false*/@discardableResultprivate func _adjust(_ idx: Int) -> Bool{let maxAdjustIdx = Int(ceilf(Float(_arr.count) / 2) - 1);if idx > maxAdjustIdx || idx < 0{return false;}let leftIdx = 2 * idx + 1;let rightIdx = 2 * idx + 2;let top: T? = _arr[idx];let left: T? = leftIdx < _arr.count ? _arr[leftIdx]: nil;let right: T? = rightIdx < _arr.count ? _arr[rightIdx]: nil;if let t = top {if let l = left, let r = right {let v = self._type == .big ? max(t, l, r) : min(t, l, r);switch v {case l:swapArr(arr: &_arr, f: leftIdx, t: idx);_adjust(leftIdx);return true;case r:swapArr(arr: &_arr, f: rightIdx, t: idx);_adjust(rightIdx);return true;default:break;}}else if let l = left {let b = self._type == .big ? (l > t) : (l < t);if b {swapArr(arr: &_arr, f: leftIdx, t: idx);_adjust(leftIdx);return true;}}else if let r = right {let b = self._type == .big ? (r > t) : (r < t);if b {swapArr(arr: &_arr, f: rightIdx, t: idx);_adjust(rightIdx);return true;}}}return false;}/*** 创建堆，依次调整 n/2 -> 0 元素*/private func _create(){let maxAdjustIdx = Int(ceilf(Float(_arr.count) / 2) - 1);for i in stride(from: maxAdjustIdx, to: -1, by: -1){_adjust(i);}}/*** 弹出一个元素，移除顶部元素，然后令顶部元素等于最后一个元素，最后调整顶部元素* @return [T?] 返回顶部元素*/func pop() -> T? {let first = _arr.first;if first != nil {if _arr.count <= 1 {_arr.removeLast();}else{swapArr(arr: &_arr, f: 0, t: _arr.count - 1);_arr.removeLast();_adjust(0);}}return first;}/*** 插入一个元素，插入到尾部，依次调整该元素的顶部元素，直到无需调整或下标为0* @param {T} - t 插入的元素*/func push(_ t: T){_arr.append(t);var idx = Int(ceilf(Float(_arr.count - 1) / 2) - 1);while true {if !_adjust(idx){break;}if idx == 0{break;}idx = Int(ceilf(Float(idx) / 2) - 1);}}/*** 返回当前元素数量* @return {Int} 返回堆内元素数量*/func count() -> Int{return _arr.count;}
}
3.2使用js实现
//常量
const BigHeap = 1;
const SmallHeap = 2;//构造函数
function Heap(type, arr, compareFunction){this.type = type;this.arr = arr;this.compareFunction = compareFunction;this._createHeap(arr);
}//数组交换
Heap._swap = function(i,j,arr){let tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}//比较值
Heap.prototype._compare = function(v1, v2){if(this.type == SmallHeap){if(v2 == null){return true;}else{if(this.compareFunction){return this.compareFunction(v1, v2) == -1;}else{return v1 < v2;}}}else{if(v2 == null){return true;}else{if(this.compareFunction){return this.compareFunction(v1, v2) == 1;}else{return v1 > v2;}}}
}//调整堆的第i个结点
Heap.prototype._adjustNode = function(i, arr){let leftChildIdx = 2 * i + 1;let leftValue = null;if(leftChildIdx < arr.length){leftValue = arr[leftChildIdx];}let rightChildIdx = 2 * i + 2;let rightValue = null;if(rightChildIdx < arr.length){rightValue = arr[rightChildIdx];}if(!leftValue && !rightValue){return;}let exchangeIdx = null;//左值存在并且大于根结点if(leftValue && this._compare(leftValue, arr[i])){//右值存在并且大于左结点if(rightValue && this._compare(rightValue, leftValue)){//右值交换exchangeIdx = rightChildIdx;}else{//左值交换exchangeIdx = leftChildIdx;}}else if(rightValue && this._compare(rightValue, leftValue)){//右值交换exchangeIdx = rightChildIdx;}if(exchangeIdx != null){Heap._swap(exchangeIdx, i, arr);//交换完毕后，新的子结点也需要调整this._adjustNode(exchangeIdx, arr);}
}//根据数组创建堆
Heap.prototype._createHeap = function(arr){let len = arr.length;if(len <= 1){return;}//最后一个非叶子结点let lastNonLeafIdx = Math.floor(len / 2) - 1;//依次调整每个结点for (let index = lastNonLeafIdx; index >= 0; index--) {this._adjustNode(index, arr);}
}//插入
Heap.prototype.insert = function(ele){this.arr.push(ele);let adjustIdx = this.arr.length;while(adjustIdx > 0){adjustIdx = Math.ceil(adjustIdx / 2) - 1;this._adjustNode(adjustIdx, this.arr);if(adjustIdx <= 0){break;}}
}//删除
Heap.prototype.remove = function(){if(this.arr.length <= 0){return null;}let value = this.arr[0];if(this.arr.length > 1){this.arr[0] = this.arr.pop();this._adjustNode(0, this.arr);}else{this.arr.pop();}return value;
}//是否为空
Heap.prototype.empty = function(){return this.arr.length == 0 || this.arr[0] == null;
}
4.0 复杂度分析
- 数组转堆的复杂度
- 首先需要进行n/2次堆的调整
- 每次调整堆最多可能需要 logn次的二次调整
- 所以时间复杂度小于 O(nlogn)
- 每次调整堆最少可能需要1次调整
- 所以时间复杂度大于O(n/2)
- 实际上，需要少量调整的操作数远远大于需要多次调整的操作。
- 根据调整规则，设最高高度为h = logn
- 根节点需要调整次数为：2^0*h
- 第二层需要调整次数为：2^1*(h-1)
- … …
- 第logn层需要调整次数为：2^(h-1)*1
- 总次数count=2^0h + 2^1(h-1) + 2^2*(h-2) + … + 2^(h-1)*(h-(h-1)) //使用错位相减
- count2 = 2^1h + 2^2*(h-1) + 2^3*(h-2) + … + 2^h*(h-(h-1))
- count = count2-count = 2^1 + 2^2 + … + 2^(h-1) + 2^h - 2^0h
- count = 2^(h+1) - 2 - h
- count = 2n - 2 - logn
- 所以时间复杂度为O(n)
- 堆的插入：O(logn)
- 堆的删除：O(logn)
相关文章：
cookie 和session 的区别详解
转自 https://www.cnblogs.com/shiyangxt/archive/2008/10/07/1305506.html 这些都是基础知识，不过有必要做深入了解。先简单介绍一下。 二者的定义： 当你在浏览网站的时候，WEB 服务器会先送一小小资料放在你的计算机上，Cookie 会…
如何设置Java Spring Boot JWT授权和认证
In the past month, I had a chance to implement JWT auth for a side project. I have previously worked with JWT in Ruby on Rails, but this was my first time in Spring. 在过去的一个月中，我有机会为辅助项目实现JWT auth。 我以前曾在Ruby on Rails中使用…
算法（5）哈希表
1.0 问题描述 实现数据结构：哈希表。 2.0 问题分析 哈希表可以看作我们经常使用的字典（swift）或对象（js），可以让一个key&value对一一对应，可以快速根据key找到value。哈希表内部使用数组…
《面向对象程序设计》c++第五次作业___calculator plus plus
c第五次作业 Calculator plusplus 代码传送门 PS:这次作业仍然orz感谢一位同学与一位学长的windows帮助，同时再次吐槽作业对Mac系统用户的不友好。（没朋友千万别用Mac！！！） 还有想吐槽作业对规范的要求大大超…
联合体union和大小端（big-endian、little-endian）
1.联合体union的基本特性——和struct的同与不同union，中文名“联合体、共用体”，在某种程度上类似结构体struct的一种数据结构，共用体(union)和结构体(struct)同样可以包含很多种数据类型和变量。在成员完全相同的情况下，struct比…
前端面试的作品示例_如何回答任何技术面试问题-包括示例
前端面试的作品示例Technical interviews can be extremely daunting. From the beginning of each question to the end, its important to know what to expect, and to be aware of the areas you might be asked about. 技术面试可能会非常艰巨。 从每个问题的开始到结束&a…
$(shell expr $(MAKE_VERSION) \= 3.81) 这里“\”的解释
android/build/core/main.mk $(shell expr $(MAKE_VERSION) \> 3.81) 为什么要加多一个“\”,因为">"会被shell解析为重定向符号，所以需要转义或用引号包围 所以，也可以这样写$(shell expr $(MAKE_VERSION) “>” 3.81)转载于:https:…
iOS应用模块化的思考及落地方案（一）模块的划分及模块化工作流程
1.0 什么是模块化 很多关于重构及设计模式的介绍中，经常提到的几个词语是复用及解耦。 模块化之所以被提出，也更多是为了解决这几个问题。 复用可以减少重复造轮子的情况，很容易理解的是，我们经常使用的github上的第三方框架&a…
Swiper 用法
部分常用API ininialSlide: 2, //起始图片切换的索引位置（起始从0开始，默认为0） autoplay: 3000, //设置自动切换时间，单位毫秒 speed: 1000, //设置滑动速度 continuous: true, //无限循环的图片切换效果 disableScroll: true, /…
node/js 漏洞_6个可用于检查Node.js中漏洞的工具
node/js 漏洞Vulnerabilities can exist in all products. The larger your software grows, the greater the potential for vulnerabilities. 所有产品中都可能存在漏洞。 您的软件增长得越大，潜在的漏洞就越大。 Vulnerabilities create opportunities for expl…
发现一个浏览器很奇怪的问题
浏览器有8个请求状态为pending时，在另一个tab中，请求就发布出去了，一直是stalled。直到pending状态变成了cancled状态。 试了360浏览器（谷歌内核）和chrome浏览器，都是这样。 具体的原因待深究 参考…
wamp配置虚拟主机
因为wampserver的php版本一直是5.x版本；因此转投xmapp用了一段时间； 意外发现wampserver3更新了；php也终于更新到7了； 果断还是决定回到wampserver的怀抱； 然后有意外的发现了wampserver3有了新功能；可以方…
iOS应用模块化的思考及落地方案（二）模块化自动构建工具的使用
1.0 iOS模块化中的问题 前文已经介绍了模块化的流程及一些常见的问题，我们在这里再次总结一下。 在工作中，当我们开始一个新项目的时候，最先考虑的就是模块化工作。 模块化工作的想法是很美好的，可是执行过程中会遇到很多的问题…
aws fargate_我如何在AWS Fargate上部署＃100DaysOfCloud Twitter Bot
aws fargateAfter passing my last certification, I asked myself how much time I spent studying cloud computing.通过上一份认证后，我问自己自己花了多少时间研究云计算。 More than 100 days!超过100天！ It also made me realize two things:这也…
think in Java 第五章之垃圾回收类型
1.引用计数： 每个对象都含有一个引用计数器，当有引用连接至对象时，引用计数加1，当引用离开作用域或被置为null时，引用计数减1. 缺陷：在对象循环引用时，存在“对象应该被回收，引用计数…
Yii 错误页面处理
【错误页面处理】 訪问一个错误的控制器 訪问一个错误的方法 有些控制器和方法禁止訪问 以上訪问会提示错误信息 404 403 以上错误信息是不方便给外边用户看到的。 1. 安全隐患 2. 用户体验不好 错误信息在site/error这个地方定义的。如今我们要自己定义错误页面来显示我们的错…
设置RGBColor
#define kUIColorFromRGB(rgbValue) [UIColor \colorWithRed:((float)((rgbValue & 0xFF0000) >> 16))/255.0 \green:((float)((rgbValue & 0xFF00) >> 8))/255.0 \blue:((float)(rgbValue & 0xFF))/255.0 alpha:1.0]
自学成才翁_作为一名自学成才的开发者从“我的旅程”中吸取的教训
自学成才翁The path of the self-taught developer is tough and filled with uncertainty. There is no straight line from newbie to career programmer. Because of this, I believe all self-taught developers have a unique story to tell.自学成才的开发者之路艰难而充…
67）vector的begin（） end（） 和 front（） back（）的区别 rbegin（） rend（）
1） 2）v1.begin() 和v1.end（） 是作为迭代器v1的 第一个位置 和 最后一个元素的下一个位置。 v1.front() 是v1这个动态数组的第一个元素的值 v1.back()是v1的最后一个元素的值。 3） 4）正向和反向的使…
倒置函数reverse的用法
倒置字符串函数reverse：用于倒置字符串s中的各个字符的位置，如原来字符串中如果初始值为123456，则通过reverse函数可将其倒置为654321，程序如下：#include<stdio.h>#include<string.h>void reverse(char s[…
设置tabbaritem的title的颜色及按钮图片
设置title颜色： [[UITabBarItem appearance] setTitleTextAttributes:{NSForegroundColorAttributeName : kUIColorFromRGB(0xb2151c)} forState:UIControlStateSelected]; 设置按钮图片： UIImage *commonImage [UIImage imageNamed:[NSString strin…
helm部署仓库中没有的包_Kubernetes的Helm软件包管理器简介
helm部署仓库中没有的包Before we dive into the Helm package manager, Im going to explain some key concepts to deploying any application anywhere. Ill also give you a brief introduction to Kubernetes terminology.在深入研究Helm软件包管理器之前 ，我将…
mem 族函数的实现
1.void * memcpy ( void * dest, const void * src, size_t num ); 头文件：#include <string.h>memcpy() 用来复制内存，memcpy() 会复制 src 所指的内存内容的前 num 个字节到 dest 所指的内存地址上。memcpy() 并不关心被复制的数据类型ÿ…
快排递归非递归python_Python递归神经网络终极指南
快排递归非递归pythonRecurrent neural networks are deep learning models that are typically used to solve time series problems. They are used in self-driving cars, high-frequency trading algorithms, and other real-world applications.循环神经网络是深度学习模型…
我的hadoop学习之路
Hadoop实现了一个分布式文件系统（Hadoop Distributed File System），简称HDFS。HDFS有高容错性的特点，并且设计用来部署在低廉的（low-cost）硬件上。 Hadoop的框架最核心的设计就是：HDFS和MapRedu…
日期处理工具类 -【二】
1、返回本周的第一天(周日为每周第一天) 1 /**2 * 返回本周的第一天(周日为每周第一天)3 * return4 */5 public static String getTheFirstDayOfThisWeek(){6 SimpleDateFormat format new SimpleDateFormat("yyyy-MM-dd");7 Calendar cal Calendar.get…
超越对手pdf_如何创建一个超越竞争对手的移动应用
超越对手pdfThe amount of time people spend on their mobile phones has increased over the years, and so has the number of people using mobile devices.多年来，人们在手机上花费的时间增加了，使用移动设备的人数也增加了。 It’s safe to say t…
vue路由对象（$route）参数简介
路由对象在使用了 vue-router 的应用中，路由对象会被注入每个组件中，赋值为 this.$route ，并且当路由切换时，路由对象会被更新。 so , 路由对象暴露了以下属性： 1.$route.path 字符串，等于当前路由对象的路…
join......on 后面的and 和where的区别
a.where 是在两个表join完成后，再附上where条件。 b. and 则是在表连接前过滤A表或B表里面哪些记录符合连接条件，同时会兼顾是left join还是right join。即 假如是左连接的话，如果左边表的某条记录不符合连接条件，那么它不…
block的运用
cell的.h文件 typedef void(^ActivityCellBlock)(NSString *str); interface ActivityCell : UITableViewCell property (nonatomic,strong) NSArray *labelAry; property (nonatomic,copy) ActivityCellBlock myBlock; -(void)showCell:(ActivityCellBlock)myBlock; cel…