好的,所以,我说有一个文本文件(不一定包含所有可能的符号),我想计算每个符号的频率,并且在计算频率之后,我需要从最常见的频率访问每个符号及其频率至少频繁.符号不一定是ASCII字符,它们可以是任意字节序列,尽管长度相同.

我正在考虑做这样的事情(伪代码):

function add_to_heap (symbol)
    freq = heap.find(symbol).frequency
    if (freq.exists? == true)
        freq++
    else
        symbol.freq = 1
        heap.insert(symbol)

MaxBinaryHeap heap
while somefile != EOF
    symbol = read_byte(somefile)
    heap.add_to_heap(symbol)
heap.sort_by_frequency()

while heap.root != empty
    root = heap.extract_root()
    do_stuff(root)

我想知道:有没有更好,更简单的方法来计算和存储文件中每个符号出现的次数？

Java的PriorityQueue构造函数的复杂性是Collection多少？我用了构造函数:

PriorityQueue(Collection<? extends E> c)

复杂度是O(n)还是O(n*log(n))？

我已经读过二元堆在删除最小操作时更快，而 d-ary 堆在降低优先级操作时更快（虽然我不明白为什么），但是我还读到了 4 堆在它们都与二进制堆相比。

那么什么时候使用二元堆，什么时候使用 d 元堆呢？我如何决定 d 堆的 d 应该是什么？

按照我的理解，

二叉堆（数据结构）用于表示优先队列ADT。它是一棵满足堆性质的完全二叉树。

堆属性- 如果 A 是 B 的父节点，则节点 A 的键（值）相对于节点 B 的键进行排序，并在整个堆中应用相同的排序。

首先，它可以帮助我记住术语heap，如果将这个数据结构称为heap是有原因的。因为，我们也使用术语堆内存。

堆的字典含义 - 杂乱无章的东西堆在一起。

题，

在学习了 Reb-Black 树和 AVL 树数据结构后，

为什么我们会想到新的数据结构（二进制堆）？

二叉堆是否解决了红黑树或 AVL 树不适合的一系列问题？

的背景

根据维基百科和我发现的其他来源,通过从空的二进制堆开始并将n个元素插入其中来构建n个元素的二进制堆是O(n log n),因为二进制堆插入是O(log n)你做了n次.我们称之为插入算法.

它还提供了一种替代方法,您可以向下/向下/向下/向下堆积/向下堆积/向下压缩元素的第一个/上半部分,从中间元素开始并以第一个元素结束,这是O(n),复杂度要高得多.这种复杂性的证明取决于每个元素的接收器复杂性取决于它在二进制堆中的高度的洞察力:如果它接近底部,它将很小,可能为零; 如果它靠近顶部,它可能很大,也许是log n.关键是在这个过程中沉没的每个元素的复杂性不是log n,因此整体复杂度远小于O(n log n),实际上是O(n).我们称之为接收器算法.

这个问题

出于同样的原因,为什么插入算法的复杂性与sink算法的复杂度不同？

考虑插入算法中前几个元素的实际工作.第一次插入的成本不是log n,它是零,因为二进制堆是空的!第二次插入的成本最差的是一次交换,第四次的成本最差是两次交换,依此类推.插入元素的实际复杂性取决于二进制堆的当前深度,因此大多数插入的复杂性小于O(log n).在插入所有n个元素之后,插入成本甚至在技术上都达不到O(log n)[它是最后一个元素的O(log(n - 1)]]!

这些节省听起来就像接收器算法所节省的成本一样,那么为什么它们对两种算法都没有统计？

尽管我已经获得了计算机科学学士学位(这在大学里有所涉及),但我从来没有能够理解二进制堆和优先级队列之间的关系.它只是...没有点击.我完全理解二进制堆是什么,我知道如何在数组中实现一个.我也知道优先队列是什么.但是他们两个如何结合在一起呢？

一个快速的谷歌查询显示了很多像这样的文章.哪种解释,但我还有更多问题:

1. 优先级队列需要确保如果添加了两个具有相同优先级的项目,则它们将按照添加它们的顺序删除.二进制堆如何确保这一点？(事实上​​,如果我没有弄错的话,那么所有项目具有相同优先级的边界情况会产生违反此规则的堆).
2. 当您从堆中删除根,然后放入最后一个元素代替根,然后需要将其与其中一个子项交换时会发生什么 - 但两个子节点具有相同的值.你如何选择与哪一个交换？(记住相同优先级项目的FIFO规则)

我在这里错过了什么？

从堆中删除叶节点的时间复杂度是多少？

我想如果你不知道节点在哪里,它就会记录,因为你必须找到它.

但是,如果你已经知道节点在哪里,它应该是O(1)对吗？既然你可以删除它而你不必重新堆积所有东西？

您如何证明具有n个节点的二进制堆恰好具有⌈n/2⌉个叶节点？

我有这个具有最大堆属性的数组.deleteMax的时间复杂度为O(logn).如果下面的代码只迭代7次,那么下面的代码(大O)的时间复杂度是多少？

int heap_size = 15;
int i, value, heap_array[]; // array is in the form of max heap
....
for(i = 0; i < 7; i++){ // iterates seven times
    value = deleteMax(heap_array);
    printf("%d ", value);
}

我脑子里有两个解决方案.第一:时间复杂度为O(7*logn)或简单为O(logn).

然后第二个是O(1/2*n*logn)或O(nlogn),因为1/2只是一个常数,我假设因为迭代次数是7,这几乎与一半相同heap_size,我可以忽略1/2.因此O(nlogn)

哪一个是正确的？

我试图证明对于二进制堆,buildHeap最多(2N-2)在元素之间进行比较.我发现很难证明这一说法.