标签: binary-heap

我已经为一堆Node*s 编写了以下代码,这些代码可以在模块中找到node:

import std.exception, std.container;

public import node;

alias NodeArray = Array!(const (Node)*);
alias NodeHeap = BinaryHeap!(NodeArray, cmp_node_ptr);

auto make_heap() {
  return new NodeHeap(NodeArray(cast(const(Node)*)[]));
}

void insert(NodeHeap* heap, in Node* u) {
  enforce(heap && u);
  heap.insert(u);
}

pure bool cmp_node_ptr(in Node* a, in Node* b) {
  enforce(a && b);
  return (a.val > b.val);
}

然后我尝试在其上运行以下单元测试,其中make_leaf返回Node*初始化的给定参数:

unittest {
  auto u = make_leaf(10);
  auto heap = make_heap();
  insert(heap, u); //bad things happen here
  assert(heap.front …

这是一个家庭作业问题,我被要求证明8元素二元堆需要进行8次比较.

但是当我使用一个例子时:1 2 3 4 5 6 7 8我不确定我是应该自下而上还是自上而下.但无论如何,我都试过了.

自上而下:我已经完成了8个步骤但是当我计算比较次数时,我得到13:S

在底部:我已经完成了7个步骤但是当我计算比较的数量时,我得到10:S

尝试算法后,我得到的比较:

1. H [L] = 8> H [i] = 4
2. H [L] = 8> H [i] = 2,H [r] = 5> H [最大] = 8
3. H [L] = 4> H [i] = 2
4. H [L] = 6> H [i] = 3,H [r] = 7> H [最大] = 6
5. H [L] = 8> H [i] = 1,H [r] = 7 <H [最大] = 8
6. H [L] = 4> H [i] = …

所以我正在开发一个程序,该程序应该"堆积"用户添加到集合中的整数等等.但是,当我尝试访问作为参数传递给函数的Node的左子节点时,我现在遇到了问题.Visual Works耗尽内存......

奇怪的是,在调试器中,我可以看到传递节点的Left子节点已创建并正确分配给传递的节点.但是当我尝试通过源代码访问它时,我得到一个疯狂的内存错误.

这是相应的代码.希望它是可读的

一旦被调用,就会发生错误的函数:

addLeftChildTo: aNode

"Determine Left child of passed node. Set that child's parent node as self. Imprint the index where that value was retrieved from the array."

| temp leftChildIndex |
2 * aNode indexOfNode <= arrayOfInput size
    ifTrue: 
        [leftChildIndex := 2 * aNode indexOfNode.
        aNode left: (arrayOfInput at: leftChildIndex).
        aNode left parentNode: aNode.                   <---VW Runs out of memory and crashes here. This occurs once the debugger dives into the 'left' accessor method of the passed …

我最近遇到一个面试问题。没有给出任何额外的信息（也许应该使用默认实现......）

在空的最小堆上（删除元素的位置已知）上的 n 个任意序列的插入和删除操作的摊销成本为：

A) 插入 O(1)，删除 O(log n)

B) 插入 O(log n)，删除 O(1)

选项（B）正确。

看到答题纸我很惊讶。我知道这很棘手，也许是空堆，也许知道要删除的元素的位置，...我不知道为什么 (A) 是假的？为什么（B）是正确的？

我对如何正确使用Binary Heap提供的内容感到有点困惑std.container.更具体地说,我想创建一个最大的整数堆,所以我尝试写

auto maxHeap = BinaryHeap!int();

并得到一个关于int不能用[]切片的编译器投诉.我试图在Phobos上阅读它的文档,但我不明白如何创建一个新的,空的二进制堆,旨在存储整数.

有人可以借给我一个手吗？

我一直在实现自己的堆模块,以帮助我理解堆数据结构.我理解它们是如何工作和管理的,但我的实现比标准python heapq模块慢得多,同时执行堆排序(对于大小为100,000的列表,heapq需要0.6s而我的代码需要2s(原来是2.6s,切断它)通过从percDown中取出len()语句并传递长度来减少到2s所以每次方法调用自身时都不必计算len.这是我的实现:

def percDown(lst, start, end, node):
    #Moves given node down the heap, starting at index start, until the heap property is
    #satisfied (all children must be larger than their parent)
    iChild = 2 * start + 1
    i = start
    # if the node has reached the end of the heap (i.e. no children left),
    # return its index (we are done)
    if iChild > end - 1:
        return start
    #if the second child exists and is smaller than …

我正在研究用于堆排序的 BST 树。

void heapSort(int arr[], int n){
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);  
     -----------
     ----------
}

它表明，树的第 2 个最后一级索引的最右边节点总是n/2-1。

请谁能告诉我简单的数学证明。谢谢

我使用标准BinaryHeap作为算法的一部分，我需要检索最大的对象（通过一些最大的定义）。两个非等价元素可能都一样大（因此它们在二进制堆中的相对顺序无关紧要）——例如，我可能只对多字段结构的单个字段的排序感兴趣。

因此，让我的类型实现Ord和Eq. 相反，我可能应该实施PartialOrd和PartialEq唯一。但是，唉，BinaryHeap需要它的元素是Ord！为什么会这样，使用BinaryHeap这些类型的最惯用的方法是什么？

（顺便说一句，在 C++ 中，在这种情况下我会很容易地编写自定义比较器类型，并在比较器类型上模板化优先级队列。所以我不认为我想做的在数学上或算法上是错误的。）

我试图了解一些Python的内置堆功能.当我传入一个元组列表时,它似乎不喜欢的东西(或者更可能的是,我没有正确地传递列表).这是我有的:

myList = ( ('a', 1), ('b', 2) )
heapify(myList)

我得到的错误是

TypeError:heap参数必须是列表

难道我做错了什么？是否有另一种传递元组列表的方法？

谢谢!

从头开始构造大小为N的二进制堆需要NlogN比较平均值,从而比较线性时间.

鉴于大小为N的两个二进制堆已经到位,如何在线性时间内构建包含所有2N密钥的单个二进制堆(使用线性比较数)？