>

>
1x
go to beginning previous frame pause play next frame go to end

二叉(最大)堆是一个维持最大堆属性完全二叉树


二叉堆是实现高效优先队列(PQ)抽象数据类型(ADT)的一种可能的数据结构。在PQ中,每个元素都有一个“优先级”,优先级较高的元素在优先级较低的元素之前被服务(平局可以简单地随意解决,或者按照普通队列的先进先出(FIFO)规则解决)。尝试点击 ExtractMax(),查看上面随机二叉堆提取最大值的示例动画。


为了集中讨论范围,这个可视化展示了一个允许重复的整数二叉最大堆。查看这个,了解如何轻松转换为二叉最小堆。通常,任何可以比较的其他对象都可以存储在二叉最大堆中,例如,浮点数的二叉最大堆等。


Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

完全二叉树:二叉树中的每一层,除了可能的最后/最低层,都被完全填满,且最后一层的所有顶点尽可能地靠左。


二叉最大堆属性:每个顶点的父顶点(除了根)包含的值大于(或等于 —— 我们现在允许重复)该顶点的值。这比以下的替代定义更容易验证:一个顶点的值(除了叶子/叶子)必须大于(或等于)其一个(或两个)子节点的值。


Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

优先队列 (PQ) 抽象数据类型 (ADT) 与普通队列 ADT 类似,但有以下两个主要操作:

  1. Enqueue(x):将新元素(键)x放入 PQ(按某种顺序),
  2. y = Dequeue():返回 PQ 中具有最高优先级(键)的现有元素 y,如果有并列,返回任意一个。

讨论:一些 PQ ADT 在 PQ 中最高优先级(键)并列的情况下,会恢复到普通队列的先进先出 (FIFO) 行为。保证在最高优先级(键)相等的情况下的稳定性是否使 PQ ADT 更难实现?


Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.


Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

想象一下:你是一名在机场控制塔T工作的空中交通管制员 (ATC)。你已经安排飞机X/Y分别在接下来的3/6分钟内降落。两架飞机的燃料都足够飞行至少接下来的15分钟,而且都离你的机场只有2分钟的路程。你观察到你的机场跑道目前是清晰的。



如果你不知道,飞机可以被指示在机场附近保持飞行模式,直到指定的降落时间。

🕑

你必须参加现场讲座才能弄清楚接下来会发生什么...


将向你提供两个选项,你需要做出决定:

  • 如果你选择选项A,举手并挥手,
  • 如果你选择选项B,举手但不挥手,

如果这两个选项都不合理,那就什么都不做。

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

除了你刚才看到的关于ATC(仅在现场讲座中)的内容外,优先队列 ADT在现实生活中还有几种潜在的用途。


讨论:你能提出几个其他需要优先队列的现实生活情况吗?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑
我们可以用数组(头尾相连数组)或者链表来构造优先队ADT(抽象数据结构)但是入列队和出列队会比较慢  O(N
 
讨论:为什么?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

现在,让我们查看上面的(随机)二叉(最大)堆的可视化。你应该看到一个完全二叉树,除根节点外的所有顶点都满足最大堆属性(A[parent(i)] ≥ A[i])。可能会出现重复的整数键。


你可以 Toggle the Visualization Mode 在直观的完全二叉树形式和基于紧凑数组实现的二叉(最大)堆之间切换。


Quiz: Based on this Binary (Max) Heap property, where will the largest integer be located?

At one of the leaf
At the root
Can be anywhere
🕑
要记住的重要知识点:如果我们有一个含有N个元素的二叉堆,因为我们要把它储存成一个完整的二叉树,所以他的高度不会高过 O(log N)
简单分析:一个满的(不止是完整的)含有N个元素的二叉树的高度 h 总是 N = 2(h+1)-1,所以 h = log2(N+1)-1 ~= log2 N。
看上面的例子 N = 7 = 2(2+1)-1 或者 h = log2(7+1)-1 = 2.
对于有关二叉堆的操作 以上知识点很重要。
🕑

完全二叉树可以作为紧凑数组A有效地存储,因为完全二叉树的顶点/紧凑数组的元素之间没有间隙。为了简化下面的导航操作,我们使用基于1的数组。VisuAlgo在每个顶点下方以红色标签显示每个顶点的索引。按照从1到N的排序顺序阅读这些索引,然后你会看到从上到下,从左到右的完全二叉树的顶点。为了帮助你理解这一点,Toggle the Visualization Mode几次。


这样,我们可以使用简单的索引操作(借助位移操作的帮助)实现基本的二叉树遍历操作:

  1. parent(i) = i>>1,索引i除以2(整数除法),
  2. left(i) = i<<1,索引i乘以2,
  3. right(i) = (i<<1)+1,索引i乘以2并加1。

专业提示:尝试在两个浏览器窗口上打开两个VisuAlgo的副本。尝试在两种不同的模式下可视化同一个二叉最大堆,并进行比较。

🕑

在这个可视化中,你可以执行几个二叉(最大)堆操作:

  1. Create(A) - O(N log N) 版本(N 次调用下面的 Insert(v)
  2. Create(A) - O(N) 版本
  3. Insert(v) 在 O(log N) 中 — 你可以插入重复项
  4. 3个版本的 ExtractMax()
    1. 一次,在 O(log N) 中
    2. K 次,即 PartialSort(),在 O(K log N) 中,或者
    3. N 次,即 HeapSort(),在 O(N log N) 中
  5. UpdateKey(i, newv) 在 O(log N 中,如果 i 已知)
  6. Delete(i) 在 O(log N 中,如果 i 已知)

还有一些其他可能的二叉(最大)堆操作,但是我们目前在某个NUS模块中出于教学原因并未详细说明。

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Insert(v): 当我们在往最大二叉堆插入元素 v 的时候 我们只能插入到最后一个元素 N + 1 来维持一个紧凑的数组 = 完整二叉树特性。然而 最大堆的特性仍然可能没被满足。这时我们从插入点往上去修复最大堆特性(如果需要的话)直到整个堆符合最大堆特性。现在点 Insert(v) 几次来插入几个随机的 v 进去现在显示的最大二叉堆。


这个向上走并且修复最大堆特性的操作没有公认的名字。我们叫它 ShiftUp (上移)但是还有人叫它 BubbleUp 或者 IncreaseKey 操作.

🕑
你明白为什么当你插入的新元素违反了最大堆的特性的时候 从插入点(第N+1个元素)往上(最多上到根元素)走,把当前顶点和它的父顶点换位 永远是正确的方法?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

Insert(v) 的时间复杂度是 O(log N)。

讨论:你理解这个推论吗?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

ExtractMax(): 提取并删除最大二叉堆中的最大元素(根)的操作需要一个在堆中的元素来替换根,不然最大堆(一个完整的二叉树,在中文中的'林‘)会变成两个断开的子树(中文中两个'木’)。这同样也是这个元素必须是最后一个元素N的原因:维持紧凑数组 = 完整二叉树性质。

因为我们要把最大二叉堆中的一个叶顶点晋升成根顶点,它很可能是会违背最大堆特性。ExtractMax() 这时从根往下比较当前值和它的两个子元素的值(如果必要的话)来修复最大二叉堆特性。现在在当前显示的最大二叉堆中试试 ExtractMax()

这个向下走并修复最大堆特性的操作没有公认的名字。我们叫它 ShiftDown (下移)但是还有人叫它 BubbleDown 或者 Heapify 操作。.

🕑
在向下运动修复最大堆特性的时候,为什么当一个顶点有两个子元素的时候,我们必须检查(甚至交换)它两个子元素中较大的那个?
为什么我们不能只比较左(或者右,如果存在的话)顶点?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

ExtractMax() 的时间复杂度是 O(log N)。

讨论:你理解这个推论吗?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

到目前为止,我们有一个数据结构,可以有效地实现优先队列 (PQ) ADT的两个主要操作:

  1. 对于Enqueue(x),我们可以在 O(log N) 时间内使用Insert(x),和
  2. 对于y = Dequeue(),我们可以在 O(log N) 时间内使用y = ExtractMax()

然而,我们可以用二叉堆做更多的操作。

🕑

Create(A): 用含有 N 个逗号分隔的数组 A 从一个空的最大二叉堆开始创建一个合法的最大二叉堆


有两种方法完成创建操作一个简单但是慢 -> O(N log N) 另一个用更复杂的技术但是快 -> O(N).


教你一招:在两个浏览器里面同时打开 VisuAlgo。用最差情况 '已排序例子' 去执行不同版本的 Create(A),你会看到可怕的差距。

🕑

Create(A) - O(N log N):简单地插入(即,通过调用 Insert(v) 操作)输入数组中的所有 N 个整数到一个最初为空的二叉最大堆中。


分析:这个操作显然是 O(N log N),因为我们调用 O(log N) Insert(v) 操作 N 次。让我们来看看 '排序示例',这是这个操作的一个难点(现在试试 Hard Case - O(N log N),我们展示了一个案例,其中 A = [1,2,3,4,5,6,7] -- 请耐心等待,因为这个示例需要一些时间来完成)。如果我们按递增顺序将值插入到一个最初为空的二叉最大堆中,那么每次插入都会触发一条从插入点(一个新的叶子)向上到根的路径。

🕑

Create(A) - O(N):这个更快的Create(A)操作版本是由Robert W. Floyd在1964年发明的。它利用了一个紧凑数组 = 完全二叉树和所有叶子(即,一半的顶点 - 见下一张幻灯片)默认为二叉最大堆的事实。然后,此操作仅从最后一个内部顶点回到根部修复二叉最大堆属性(如果需要)。


分析:一个松散的分析给出了另一个O(N/2 log N) = O(N log N)的复杂性,但实际上只是O(2*N) = O(N) - 在接下来的几张幻灯片中有详细信息。现在尝试在相同的输入数组A = [1,2,3,4,5,6,7]上使用 Hard Case - O(N),并看到在与前一张幻灯片相同的困难情况下(但不是生成最大交换次数的情况 - 你自己尝试'对角线条目'测试用例),这个操作远优于O(N log N)版本。

🕑

简单证明为什么在最大堆中(里面N个元素)一半的元素都是叶元素(为了概括性,我们假设N是偶数):

假设最后一个叶元素的序号是 N, 那么它的父元素的序号是 i = N/2 (回忆 这节课). 它的左子元素的序号是 i+1, 如果存在的话 (它其实并不存在), 将会是 2*(i+1) = 2*(N/2+1) = N+2, 这个结果超过了 N (最后一个叶元素) 所以 i+1 一定是一个没有子元素的叶元素。因为二叉堆的序号是连续的,所以序号s [i+1 = N/2+1, i+2 = N/2+2, ..., N], 或者说一半的顶点,都是叶元素。

🕑
首先,我们回忆含有N个元素的满二叉树的高度是log2 N.
其次,要明白运行shiftDown(i)操作所需要的时间不是最高值O(log N), 而是 O(h),h是在以顶点 i 为跟的从树的高度。
最后,在一个高度为 h 的满二叉树中 有ceil(N/2h+1)个顶点。
在上面这个满二叉树的例子中 N = 7, h = 2。 顶点数量为 ceil(7/20+1) = 4 分别是在h = 0  {44,35,26,17} 。在高度h = 1ceil(7/21+1) = 2 个顶点 分别是: {62,53} 在高度h = 2  ceil(7/22+1) = 1 个顶点 它是 {71}。
🕑

Create(A) 用 O(N) 的版本是这样:


analysis


如果以上公式太复杂的话,现代学生会想到用 WolframAlpha 来解决。

🕑

堆排序函数HeapSort() John William Joseph Williams 在1964年发明了堆排序算法和这个二叉堆数据结构. 堆排序的操作 (假定最大二叉堆已经在O(n)的时间复杂度内建立)非常简单。只需要调用提取堆顶函数ExtractMax() n次即可,每次的时间复杂度为O(log N). 现在你可以试一下屏幕上的这个最大二叉堆 HeapSort()


分析:堆排序显然是O(N log N) - 一个最优的通过比较来排序的算法 

Quiz: In worst case scenario, HeapSort() is asymptotically faster than...

Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
🕑

尽管 HeapSort() 在最好/平均/最坏 情况下的时间复杂度都是 θ(N log N) ,它真的是最好的用比较元素的方法来实现的排序算法吗?


讨论点:HeapSort()的缓存性能如何?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

实际上,如果我们只对二叉(最大)堆中的前K个最大元素感兴趣,我们只需调用O(log N)的ExtractMax()操作K次。现在尝试在当前显示的二叉(最大)堆上执行PartialSort()。这个操作被称为PartialSort()。


简单分析PartialSort()显然以O(K log N)运行 - 这是一个输出敏感的算法,其中时间复杂度取决于输出大小K

🕑
现在你已经到了最大二叉堆基础知识这章的结尾,我们希望你可以在探索模式中探索更多。
然而我们还有一些更有趣的最大二叉堆的挑战,这些在这章节列出。

当你全部学会了的时候,我们邀请你学习更高级的算法,它们用优先队做底层数据结构(之一),例如 Prim's MST algorithm, Dijkstra's SSSP algorithm, A* 搜索算法(还不在 VisuAlgo里), 一些贪婪算法,等等.

🕑
如果我们只处理数字(包括这个只接受整数的动画),转换最大二叉堆变为最小二叉堆很容易 不需要改任何东西,反之亦然。
我们可以取每一个元素的相反数去重新构造一个二叉堆。如果最开始我们用的是最大二叉堆,那么结果就是最小二叉堆(忽视负号,见上图),反之亦然。
🕑
对于一些优先队列的应用场景,我们需要修改(增加或降低)一个已经在(最大)二叉堆里的值的优先度。如果我们知道此值的序号i,我们可以利用以下简单的策略:更新A[i] = newv,然后shiftUp(i)shiftDown(i),只有一个恢复最大堆的动作会成功 - 如果newv > / < A[parent(i)]/A[i更大的子值] shiftUp(i)/shiftDown(i)会被触发。

所以,UpdateKey(i, newv)可以在O(log N)内完成,如果我们已知序号i
🕑
对于一些优先队列的应用场景,我们需要修改(增加或降低)一个已经在(最大)二叉堆里的值的优先度。如果我们知道此值的序号i,我们可以利用以下简单的策略:更新A[i] = A[1]+1(一个比当前根更大的值)。然后shiftUp(i)(实际上是UpdateKey(i, A[1]+1)。这样会使序号i变成新的根,然后我们可以ExtractMax()一次来删除它。

所以,Delete(i)可以在O(log N)内完成,前提是我们已知序号i

讨论:对于UpdateKey(i, newv)Delete(i),如果我们只有oldv,必须搜索它在最大二叉树中的的位置,会怎样?可以比O(N)更快吗?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

如果你正在寻找二叉(最大)堆的实现来实际模拟优先队列,那么有个好消息。


C++ 和 Java 已经有内置的优先队列实现,很可能使用了这种数据结构。它们是 C++ STL priority_queue(默认是最大优先队列)和 Java PriorityQueue(默认是最小优先队列)。然而,内置的实现可能不适合有效地执行一些 PQ 扩展操作(在某个 NUS 课程中出于教学原因省略了详细信息)。


Python 的 heapq 存在,但其性能相当慢。OCaml 没有内置的优先队列,但我们可以使用将在 VisuAlgo 的其他模块中提到的其他东西(省略详细信息的原因与上述相同)。


附言:堆排序可能用于 C++ STL 算法 partial_sort


然而,这是我们的 BinaryHeapDemo.cpp | py | java 的实现。

🕑
如果你想了解更多关于这个数据结构的有趣问题,你可以去这里做一些训练和测试 二叉堆 (不需要登录)。
NUS学生请登录并且通过这个单元的考试,相应的成就会被记录在你的账户里.
🕑

我们还有一些编程问题可以用到二叉堆数据结构UVa 01203 - ArgusKattis - numbertree.


试着解决它们来提高你对这个数据结构的理解。你可以用C++ STL priority_queue, Python heapq或者JAVA PriorityQueue 如果它们可以简化你的解法

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑
在漫长的最大二叉堆的课程之后,惊悚时刻到了...
最大二叉堆有可能不是实现优先队列最好的数据结构...
思考:所以用什么更好?
🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.


If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.


FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.


You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

-> 紧凑数组模式

新建(A) - O(N log N)

新建(A) - O(N)

插入(v)

提取最大值()

UpdateKey(i, newv)

Delete(i)

>
A =

前进

最佳情况:倒排序

N =

随机

最坏情况:升序排序

A =

前进

最佳情况:倒排序

N =

随机

Worst Case: Diagonal Entry

v =

前进

1x (一次
)

K =

Kx (PartialSort (部分排序))

Nx (堆排序)

i =
newv =

前进

i =

前进

关于 团队 使用条款
隐私政策

关于

VisuAlgo最初由副教授Steven Halim于2011年构思,旨在通过提供自学、互动式学习平台,帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年,VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

虽然VisuAlgo主要面向新加坡国立大学(NUS)的学生,包括各种数据结构和算法课程(例如CS1010/等价课程,CS2040/等价课程(包括IT5003),CS3230,CS3233和CS4234),但它也是全球好奇心的宝贵资源,促进在线学习。

最初,VisuAlgo并不适用于智能手机等小触摸屏,因为复杂的算法可视化需要大量的像素空间和点击拖动交互。为了获得最佳用户体验,建议使用最低分辨率为1366x768的屏幕。然而,自2022年4月以来,VisuAlgo的移动(精简)版本已经推出,使得在智能手机屏幕上使用VisuAlgo的部分功能成为可能。

VisuAlgo仍然在不断发展中,正在开发更复杂的可视化。目前,该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器,其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成,并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统,它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重,计算机科学教师可以显著提高学生对这些基本概念的掌握程度,因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言:英语、中文和印尼语。此外,我们还用各种语言撰写了关于VisuAlgo的公开笔记,包括印尼语、韩语、越南语和泰语:

id, kr, vn, th.

团队

项目领导和顾问(2011年7月至今)
Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

本科生研究人员 1
CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

最后一年项目/ UROP学生 1
Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 2
CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

最后一年项目/ UROP学生 2
Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

本科生研究人员 3
Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

最后一年项目/ UROP学生 3
Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

致谢
NUS教学与学习发展中心(CDTL)授予拨款以启动这个项目。在2023/24学年,Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

使用条款

VisuAlgo慷慨地向全球计算机科学界提供免费服务。如果您喜欢VisuAlgo,我们恳请您向其他计算机科学学生和教师宣传它的存在。您可以通过社交媒体平台(如Facebook、YouTube、Instagram、TikTok、Twitter等)、课程网页、博客评论、电子邮件等方式分享VisuAlgo。

数据结构与算法(DSA)的学生和教师可以直接在课堂上使用本网站。如果您从本网站截取屏幕截图或视频,可以在其他地方使用,但请引用本网站的URL(https://visualgo.net)和/或下面的出版物列表作为参考。但请不要下载VisuAlgo的客户端文件并将其托管在您的网站上,因为这构成了抄袭行为。目前,我们不允许他人分叉此项目或创建VisuAlgo的变体。个人使用离线副本的客户端VisuAlgo是可以接受的。

请注意,VisuAlgo的在线测验组件具有重要的服务器端元素,保存服务器端脚本和数据库并不容易。目前,普通公众只能通过“培训模式”访问在线测验系统。“测试模式”提供了一个更受控制的环境,用于在新加坡国立大学的真实考试中使用随机生成的问题和自动验证。


出版物列表

这项工作曾在2012年国际大学生程序设计竞赛(波兰,华沙)的CLI研讨会上和2012年国际信息学奥林匹克竞赛(意大利,锡尔米奥内-蒙蒂基亚里)的IOI会议上展示过。您可以点击此链接阅读我们2012年关于该系统的论文(当时还没有称为VisuAlgo),以及此链接阅读2015年的简短更新(将VisuAlgo与之前的项目关联起来)。


错误报告或新功能请求

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误,或者您想要请求新功能,请联系Steven Halim副教授。他的联系方式是将他的名字连接起来,然后加上gmail dot com。

隐私政策

版本 1.2 (更新于2023年8月18日星期五)。

自2023年8月18日(星期五)起,我们不再使用 Google Analytics。因此,我们现在使用的所有 cookies 仅用于此网站的运营。即使是首次访问的用户,烦人的 cookie 同意弹窗现在也已关闭。

自2023年6月7日(星期五)起,由于 Optiver 的慷慨捐赠,全世界的任何人都可以自行创建一个 VisuAlgo 账户,以存储一些自定义设置(例如,布局模式,默认语言,播放速度等)。

此外,对于 NUS 学生,通过使用 VisuAlgo 账户(一个 NUS 官方电子邮件地址,课堂名册中的学生姓名,以及在服务器端加密的密码 - 不存储其他个人数据),您同意您的课程讲师跟踪您的电子讲义阅读和在线测验培训进度,这是顺利进行课程所必需的。您的 VisuAlgo 账户也将用于参加 NUS 官方的 VisuAlgo 在线测验,因此,将您的账户凭据传递给他人代您进行在线测验构成学术违规。课程结束后,您的用户账户将被清除,除非您选择保留您的账户(OPT-IN)。访问完整的 VisuAlgo 数据库(包含加密密码)的权限仅限于 Halim 教授本人。

对于全球其他已经给 Steven 写过信的 CS 讲师,需要一个 VisuAlgo 账户(您的(非 NUS)电子邮件地址,您可以使用任何显示名称,以及加密密码)来区分您的在线凭据与世界其他地方。您的账户将具有 CS 讲师特定的功能,即能够查看隐藏的幻灯片,这些幻灯片包含了在隐藏幻灯片之前的幻灯片中提出的问题的(有趣的)答案。您还可以访问 VisuAlgo 在线测验的 Hard 设置。您可以自由地使用这些材料来增强您的数据结构和算法课程。请注意,未来可能会有其他 CS 讲师特定的功能。

对于任何拥有 VisuAlgo 账户的人,如果您希望不再与 VisuAlgo 工具有关联,您可以自行删除您的账户。