- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
如果堆基于数组并且根被提取,我使用的代码假设重新排列节点以便维护堆属性。
根据我的理解,数组和堆并不完全相同,但在代码中,构建堆似乎只是重新排列数组,使其拥有堆属性。这是创建堆的标准方法吗?是否有必要填充另一个数组而不是仅仅改变它所基于的数组?
我很难理解这个概念,因为当我使用函数 extract-max
删除根时,除非我从数组中弹出元素,否则数组的大小保持不变。并且堆应该更小,但所发生的只是向上移动以替换根的节点在数组中由零指示并且它没有被删除。
如果我确实保留堆基本上是服从堆属性的数组的结构,我该如何删除不应再属于堆的节点?在我的代码中,此节点在打印数组时由 0
表示。
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"
int parent(int i)
{
return (i - 1) / 2;
}
int left(int i)
{
if(i == 0)
return 1;
else
return 2*i;
}
int right(int i)
{
if(i == 0)
return 2;
else
return 2*i + 1;
}
void max_heapify(std::deque<int> &A, int i, int heapsize)
{
int largest;
int l = left(i);
int r = right(i);
if(l <= heapsize && A[l] > A[i])
largest = l;
else
largest = i;
if(r <= heapsize && A[r] > A[largest])
largest = r;
if(largest != i) {
exchange(A, i, largest);
max_heapify(A, largest, heapsize);
}
}
void build_max_heap(std::deque<int> &A)
{
int heapsize = A.size() - 1;
for(int i = (A.size() - 1) / 2; i >= 0; i--)
max_heapify(A, i, heapsize);
}
int heap_extract_max(std::deque<int> &A, int heapsize)
{
if(heapsize < 0)
throw std::out_of_range("heap underflow");
int max = A.front();
//A.pop_front();
A[0] = A[heapsize--];
//A.pop_back();
max_heapify(A, 0, heapsize);
return max;
}
int main(int argc, const char * argv[])
{
std::deque<int> B = deq(7);
print(B);
build_max_heap(B);
print(B);
std::cout << "Extract max ->\t" << heap_extract_max(B, B.size()) << std::endl;
print(B);
std::cout << "Extract max ->\t" << heap_extract_max(B, B.size()) << std::endl;
print(B);
return 0;
}
输出:
79 92 86 29 27 42 6
92 86 79 29 27 42 6
Extract max -> 92
86 79 42 29 27 0 6
Extract max -> 86
79 42 27 29 0 0 6
最佳答案
您的 heap_extract_max
函数正在丢弃 std::deque
中的最后一个元素。
int heap_extract_max(std::deque<int> &A, int heapsize)
{
if(heapsize < 0)
throw std::out_of_range("heap underflow");
int max = A.front(); // Get a copy of the first element
A[0] = A[heapsize--]; // Copy the last element to the first element
// and reduce the heap size, effectively
// discarding the last element.
max_heapify(A, 0, heapsize);
return max;
}
在此之后,如果需要,您可以安全地在 std::deque
上使用 pop_back()
从容器中移除该元素。
关于c++ - 使用堆构建优先级队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18992560/
int x = 1; System.out.println( x++ + x++ * --x ); 上面的代码打印出“5”,但我不明白怎么办?我一直为最后一个 x 取零,然后乘以仍然为 0 的第二个
我现在正在尝试使用 Preference 类 首选项 pfrOfThis = Preferences.userNodeForPackage(this) 出现错误: “类 java.util.prefs
用下面的代码 import sys print "Hello " + sys.argv[1] if len(sys.argv) > 1 else "Joe" + "." 当我运行时 python he
我的网页包含: td { padding-left:10px; } 引用的样式表包含: .rightColumn * {margin: 0; padding: 0;} 我在 rightc
使用 JPA 我有一个关于 CascadeTypes 的问题。 例如: @ManyToMany(fetch=FetchType.LAZY, cascade={CascadeType.PERSIST,
下面的“括号”是怎么写的? val words = List("foo", "bar", "baz") val phrase = "These are upper case: " + words ma
我只是想知道,对于以下代码,编译器是否单独使用关联性/优先级或其他一些逻辑来评估。 int i = 0, k = 0; i = k++; 如果我们根据关联性和优先级进行评估,postfix ++具有比
我设置了一个 Azure FrontDoor 服务,以主/备份类型的方式将流量分配给两个 API 管理服务。就像我希望所有流量都流向我的主要 APIM 服务一样,如果我碰巧关闭该服务(假装中断),那么
这是一个简单的 CSS: /* Smartphones (portrait and landscape) ----------- */ @media only screen and (min-devi
我设置了一个 Azure FrontDoor 服务,以主/备份类型的方式将流量分配给两个 API 管理服务。就像我希望所有流量都流向我的主要 APIM 服务一样,如果我碰巧关闭该服务(假装中断),那么
来自 Programming Perl pg 90,他说: @ary = (1, 3, sort 4, 2); print @ary; 排序右侧的逗号在排序之前求值,而左侧的逗号在排序之
+----+------------+------+ | id | title | lang | +----+------------+------+ | 1 | title 1 EN |
如何使用 Java 获取 DiffServe 代码点 (DSCP) 整数的优先级部分?我预计它涉及位移位,但由于某种原因,我似乎无法获得我期望的值。 最佳答案 假设我理解正确,只需向右执行 3 位逻辑
我有下一个运行良好的 js 函数: $(function () { $(".country").click(function () { var countries = Arra
int a[3]={10,20,30}; int* p = a; cout << *p++ << endl; 根据 wikipedia ,后缀++的优先级高于解引用,*p++应该先运行p++再解引用结
我想在优先读取归档后解决这种类型的表达式 2+3/5*9+3-4 这是我尝试解决该任务的代码我该如何解决这个问题 while ( !inputFile.eof() ) { getline( inp
我正在玩 Rhino 并注意到这种奇怪的行为似乎是运算符优先级: js> {}+{} NaN js> ''+{}+{} [object Object][object Object] js> ''+({
我想遍历文件列表并检查它们是否存在,如果文件不存在则给出错误并退出。我写了下面的代码: FILES=( file1.txt file2.txt file3.txt ) for file in ${FI
我正在执行级联 SELECT: SELECT * FROM x WHERE a = 1 AND b = 2 AND c = 3 => If nothing found, try: SELECT * F
即将参加考试,我正在参加之前的考试。 问题: 当两个或多个样式表规则应用于同一元素时,以下哪种类型的规则将优先? 一个。任何来自浏览器的声明 b.有用户来源的正常声明 C。作者来源正常声明 d.文档级
我是一名优秀的程序员,十分优秀!