小顶堆和大顶堆是堆这种数据结构的两种形式，它们都是一颗完全二叉树，并且满足特定的性质。小顶堆的堆顶元素是最小的元素，而大顶堆的堆顶元素是最大的元素。小顶堆和大顶堆常用于实现优先队列，其操作的时间复杂度通常为O(log n)。
小顶堆和大顶堆的区别在于它们的堆顶元素分别是最小的和最大的元素。因此，小顶堆通常用于求出数据集中的最小值，而大顶堆通常用于求出数据集中的最大值。
// 大顶堆模板
class MaxHeap {
constructor() {
this.heap = [];
}
// 返回堆的大小
size() {
return this.heap.length;
}
// 向堆中插入一个新元素
insert(val) {
// 将新元素添加到堆的末尾
this.heap.push(val);
// 调整堆使其满足大顶堆的性质
this.heapifyUp();
}
// 删除堆顶元素
deleteTop() {
// 如果堆为空，则直接返回
if (this.size() === 0) return;
// 将堆顶元素与堆的最后一个元素交换
let temp = this.heap[0];
this.heap[0] = this.heap[this.size() - 1];
this.heap[this.size() - 1] = temp;
// 将堆的最后一个元素从堆中删除
this.heap.pop();
// 调整堆使其满足大顶堆的性质
this.heapifyDown();
}
// 调整堆使其满足大顶堆的性质
heapifyUp() {
// 获取新插入的元素的索引
let index = this.size() - 1;
// 循环，直到该元素的值大于等于它的父节点的值
while (index > 0 && this.heap[index] > this.heap[this.parent(index)]) {
// 将该元素与它的父节点交换
let temp = this.heap[index];
this.heap[index] = this.heap[this.parent(index)];
this.heap[this.parent(index)] = temp;
// 更新索引
index = this.parent(index);
}
}
// 调整堆使其满足大顶堆的性质
heapifyDown() {
// 获取堆顶元素的索引
let index = 0;
// 循环，直到该元素的值小于等于它的子节点的值
while (index < this.size() && this.heap[index] < this.maxChildValue(index)) {
// 获取该元素的子节点中的最大值的索引
let maxChildIndex = this.maxChildIndex(index);
// 将该元素与它的子节点中的最大值交换
let temp = this.heap[index];
this.heap[index] = this.heap[maxChildIndex];
this.heap[maxChildIndex] = temp;
// 更新索引
index = maxChildIndex;
}
}
// 返回给定索引的元素的父节点的索引
parent(index) {
return Math.floor((index - 1) / 2);
}
// 返回给定索引的元素的左子节点的索引
leftChild(index) {
return index * 2 + 1;
}
// 返回给定索引的元素的右子节点的索引
rightChild(index) {
return index * 2 + 2;
}
// 返回给定索引的元素的子节点中的最大值
maxChildValue(index) {
let leftChildIndex = this.leftChild(index);
let rightChildIndex = this.rightChild(index);
if (leftChildIndex >= this.size()) return -Infinity;
if (rightChildIndex >= this.size()) return this.heap[leftChildIndex];
return Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex]);
}
// 返回给定索引的元素的子节点中的最大值的索引
maxChildIndex(index) {
let leftChildIndex = this.leftChild(index);
let rightChildIndex = this.rightChild(index);
if (leftChildIndex >= this.size()) return -1;
if (rightChildIndex >= this.size()) return leftChildIndex;
return this.heap[leftChildIndex] > this.heap[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
}
// 小顶堆模板
class MinHeap {
constructor() {
// 初始化堆数组
this.heap = [];
}
// 获取父节点的索引
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
// 获取左子节点的索引
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1;
}
// 获取右子节点的索引
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2;
}
// 判断是否存在父节点
hasParent(index) {
return this.getParentIndex(index) >= 0;
}
// 判断是否存在左子节点
hasLeftChild(index) {
return this.getLeftChildIndex(index) < this.heap.length;
}
// 判断是否存在右子节点
hasRightChild(index) {
return this.getRightChildIndex(index) < this.heap.length;
}
// 获取左子节点的值
leftChild(index) {
return this.heap[this.getLeftChildIndex(index)];
}
// 获取右子节点的值
rightChild(index) {
return this.heap[this.getRightChildIndex(index)];
}
// 获取父节点的值
parent(index) {
return this.heap[this.getParentIndex(index)];
}
// 交换堆中两个节点的值
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
// 获取堆顶元素
peek() {
if (this.heap.length === 0) {
throw new Error('Heap is empty');
}
return this.heap[0];
}
// 取出堆顶元素，并重新排序
poll() {
if (this.heap.length === 0) {
throw new Error('Heap is empty');
}
const item = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return item;
}
// 向堆中插入新元素，并重新排序
add(item) {
this.heap.push(item);
this.heapifyUp();
}
// 从下往上重新排序
heapifyUp() {
let index = this.heap.length - 1;
// 只要当前节点有父节点，并且父节点的值比当前节点的值大，就交换它们的值
while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
this.swap(this.getParentIndex(index), index);
index = this.getParentIndex(index);
}
}
// 从上往下重新排序
heapifyDown() {
let index = 0;
// 只要当前节点有左子节点
while (this.hasLeftChild(index)) {
let smallerChildIndex = this.getLeftChildIndex(index);
// 如果当前节点有右子节点，并且右子节点的值比左子节点的值小，就把右子节点的索引赋给smallerChildIndex
if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
smallerChildIndex = this.getRightChildIndex(index);
}
// 如果当前节点的值已经比子节点的值小，就退出循环
if (this.heap[index] < this.heap[smallerChildIndex]) {
break;
} else {
// 否则交换它们的值，并继续循环
this.swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
代码如下：
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxKelements = function(nums, k) {
let score = []
let heap = new MaxHeap()
for (let item of nums) {
heap.insert(item)
}
while (k) {
let max = heap.heap[0]
score.push(max)
max = Math.ceil(max / 3)
heap.heap[0] = max
heap.heapifyDown()
k--
}
return score.reduce((item, total) => { return item + total }, 0)
};
// 大顶堆模板
class MaxHeap {
constructor() {
this.heap = [];
}
// 返回堆的大小
size() {
return this.heap.length;
}
// 向堆中插入一个新元素
insert(val) {
// 将新元素添加到堆的末尾
this.heap.push(val);
// 调整堆使其满足大顶堆的性质
this.heapifyUp();
}
// 删除堆顶元素
deleteTop() {
// 如果堆为空，则直接返回
if (this.size() === 0) return;
// 将堆顶元素与堆的最后一个元素交换
let temp = this.heap[0];
this.heap[0] = this.heap[this.size() - 1];
this.heap[this.size() - 1] = temp;
// 将堆的最后一个元素从堆中删除
this.heap.pop();
// 调整堆使其满足大顶堆的性质
this.heapifyDown();
}
// 调整堆使其满足大顶堆的性质
heapifyUp() {
// 获取新插入的元素的索引
let index = this.size() - 1;
// 循环，直到该元素的值大于等于它的父节点的值
while (index > 0 && this.heap[index] > this.heap[this.parent(index)]) {
// 将该元素与它的父节点交换
let temp = this.heap[index];
this.heap[index] = this.heap[this.parent(index)];
this.heap[this.parent(index)] = temp;
// 更新索引
index = this.parent(index);
}
}
// 调整堆使其满足大顶堆的性质
heapifyDown() {
// 获取堆顶元素的索引
let index = 0;
// 循环，直到该元素的值小于等于它的子节点的值
while (index < this.size() && this.heap[index] < this.maxChildValue(index)) {
// 获取该元素的子节点中的最大值的索引
let maxChildIndex = this.maxChildIndex(index);
// 将该元素与它的子节点中的最大值交换
let temp = this.heap[index];
this.heap[index] = this.heap[maxChildIndex];
this.heap[maxChildIndex] = temp;
// 更新索引
index = maxChildIndex;
}
}
// 返回给定索引的元素的父节点的索引
parent(index) {
return Math.floor((index - 1) / 2);
}
// 返回给定索引的元素的左子节点的索引
leftChild(index) {
return index * 2 + 1;
}
// 返回给定索引的元素的右子节点的索引
rightChild(index) {
return index * 2 + 2;
}
// 返回给定索引的元素的子节点中的最大值
maxChildValue(index) {
let leftChildIndex = this.leftChild(index);
let rightChildIndex = this.rightChild(index);
if (leftChildIndex >= this.size()) return -Infinity;
if (rightChildIndex >= this.size()) return this.heap[leftChildIndex];
return Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex]);
}
// 返回给定索引的元素的子节点中的最大值的索引
maxChildIndex(index) {
let leftChildIndex = this.leftChild(index);
let rightChildIndex = this.rightChild(index);
if (leftChildIndex >= this.size()) return -1;
if (rightChildIndex >= this.size()) return leftChildIndex;
return this.heap[leftChildIndex] > this.heap[rightChildIndex] ? leftChildIndex : rightChildIndex;
}
}
代码如下：
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var smallestK = function(arr, k) {
let res = []
let heap = new MinHeap()
for (let item of arr) {
heap.add(item)
}
while (k) {
let min = heap.heap[0]
res.push(min)
heap.heap[0] = Number.MAX_VALUE
min = heap.heap[0]
heap.heapifyDown()
k--
}
return res
};
// 小顶堆模板
class MinHeap {
constructor() {
// 初始化堆数组
this.heap = [];
}
// 获取父节点的索引
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2);
}
// 获取左子节点的索引
getLeftChildIndex(parentIndex) {
return 2 * parentIndex + 1;
}
// 获取右子节点的索引
getRightChildIndex(parentIndex) {
return 2 * parentIndex + 2;
}
// 判断是否存在父节点
hasParent(index) {
return this.getParentIndex(index) >= 0;
}
// 判断是否存在左子节点
hasLeftChild(index) {
return this.getLeftChildIndex(index) < this.heap.length;
}
// 判断是否存在右子节点
hasRightChild(index) {
return this.getRightChildIndex(index) < this.heap.length;
}
// 获取左子节点的值
leftChild(index) {
return this.heap[this.getLeftChildIndex(index)];
}
// 获取右子节点的值
rightChild(index) {
return this.heap[this.getRightChildIndex(index)];
}
// 获取父节点的值
parent(index) {
return this.heap[this.getParentIndex(index)];
}
// 交换堆中两个节点的值
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
// 获取堆顶元素
peek() {
if (this.heap.length === 0) {
throw new Error('Heap is empty');
}
return this.heap[0];
}
// 取出堆顶元素，并重新排序
poll() {
if (this.heap.length === 0) {
throw new Error('Heap is empty');
}
const item = this.heap[0];
this.heap[0] = this.heap.pop();
this.heapifyDown();
return item;
}
// 向堆中插入新元素，并重新排序
add(item) {
this.heap.push(item);
this.heapifyUp();
}
// 从下往上重新排序
heapifyUp() {
let index = this.heap.length - 1;
// 只要当前节点有父节点，并且父节点的值比当前节点的值大，就交换它们的值
while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
this.swap(this.getParentIndex(index), index);
index = this.getParentIndex(index);
}
}
// 从上往下重新排序
heapifyDown() {
let index = 0;
// 只要当前节点有左子节点
while (this.hasLeftChild(index)) {
let smallerChildIndex = this.getLeftChildIndex(index);
// 如果当前节点有右子节点，并且右子节点的值比左子节点的值小，就把右子节点的索引赋给smallerChildIndex
if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
smallerChildIndex = this.getRightChildIndex(index);
}
// 如果当前节点的值已经比子节点的值小，就退出循环
if (this.heap[index] < this.heap[smallerChildIndex]) {
break;
} else {
// 否则交换它们的值，并继续循环
this.swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为
关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request
有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳
我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_
无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非