>

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

A Binary (Max) Heap is a complete binary tree that maintains the Max Heap property.


Binary Heap is one possible data structure to model an efficient Priority Queue (PQ) Abstract Data Type (ADT). In a PQ, each element has a "priority" and an element with higher priority is served before an element with lower priority (ties are either simply resolved arbitrarily or broken with standard First-In First-Out (FIFO) rule as with a normal Queue). Try clicking ExtractMax() for a sample animation on extracting the max value of random Binary Heap above.


To focus the discussion scope, this visualization show a Binary Max Heap of integers where duplicates are allowed. See this for an easy conversion to Binary Min Heap. Generally, any other objects that can be compared can be stored in a Binary Max Heap, e.g., Binary Max Heap of floating points, etc.


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.

🕑

Complete Binary Tree: Every level in the binary tree, except possibly the last/lowest level, is completely filled, and all vertices in the last level are as far left as possible.


Binary Max Heap property: The parent of each vertex - except the root - contains value greater than (or equal to) the value of that vertex. This is an easier-to-verify definition than the following alternative definition: The value of a vertex - except the leaf/leaves - must be greater than (or equal to) the value of its one (or two) child(ren).


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.

🕑

Priority Queue (PQ) Abstract Data Type (ADT) is similar to normal Queue ADT, but with these two major operations:

  1. Enqueue(x): Put a new element (key) x into the PQ (in some order),
  2. y = Dequeue(): Return an existing element y that has the highest priority (key) in the PQ and if ties, return any.

Discussion: Some PQ ADT reverts to First-In First-Out (FIFO) behavior of a normal Queue in the event there is a tie of highest priority (key) in the PQ. Does guaranteeing stability on equal highest priority (key) makes PQ ADT harder to implement?


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.

🕑

Imagine: You are an Air Traffic Controller (ATC) working in the control tower T of an airport. You have scheduled aircraft X/Y to land in the next 3/6 minutes, respectively. Both have enough fuel for at least the next 15 minutes and both are just 2 minutes away from your airport. You observe that your airport runway is clear at the moment.

               ✈(Y)
✈(X)
(T)
<--->
|||
|||
________|||_____________

In case you do not know, aircraft can be instructed to fly in holding pattern near the airport until the designated landing time.

🕑

You have to attend the live lecture to figure out what happens next...


There will be two options presented to you and you will have to decide:

  1. Raise AND wave your hand if you choose option A,
  2. Raise your hand but do NOT wave it if you choose option B,

If none of the two options is reasonable for you, simply do nothing.

🕑

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.

🕑
除了你刚才看到的几个例子外(NUS课堂独享) 现实生活中还有很多可以用到优先队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.

🕑

Now, let's view the visualisation of a (random) Binary (Max) Heap above. You should see a complete binary tree and all vertices except the root satisfy the Max Heap property (A[parent(i)] ≥ A[i]).


You can Toggle the Visualization Mode between the visually more intuitive complete binary tree form or the underlying compact array based implementation of a Binary (Max) Heap.


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

At the root
Can be anywhere
At one of the leaf
🕑
要记住的重要知识点:如果我们有一个含有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 complete binary tree can be stored efficiently as a compact array A as there is no gap between vertices of a complete binary tree/elements of a compact array. To simplify the navigation operations below, we use 1-based array. VisuAlgo displays the index of each vertex as a red label below each vertex. Read those indices in sorted order from 1 to N, then you will see the vertices of the complete binary tree from top to down, left to right. To help you understand this, Toggle the Visualization Mode several times.


This way, we can implement basic binary tree traversal operations with simple index manipulations (with help of bit shift manipulation):

  1. parent(i) = i>>1, index i divided by 2 (integer division),
  2. left(i) = i<<1, index i multiplied by 2,
  3. right(i) = (i<<1)+1, index i multiplied by 2 and added by 1.

Pro tip: Try opening two copies of VisuAlgo on two browser windows. Try to visualize the same Binary Max Heap in two different modes and compare them.

🕑

In this visualization, you can perform several Binary (Max) Heap operations:

  1. Create(A) - O(N log N) version (N calls of Insert(v) below)
  2. Create(A) - O(N) version
  3. Insert(v) in O(log N) — you are allowed to insert duplicates
  4. 3 versions of ExtractMax():
    1. Once, in O(log N)
    2. K times, i.e., PartialSort(), in O(K log N), or
    3. N times, i.e., HeapSort(), in O(N log N)
  5. UpdateKey(i, newv) in O(log N if i is known)
  6. Delete(i) in O(log N if i is known)

There are a few other possible Binary (Max) Heap operations, but currently we do not elaborate them for pedagogical reason in a certain NUS module.

🕑

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.

🕑

Up to here, we have a data structure that can implement the two major operations of Priority Queue (PQ) ADT efficiently:

  1. For Enqueue(x), we can use Insert(x) in O(log N) time, and
  2. For y = Dequeue(), we can use y = ExtractMax() in O(log N) time.

However, we can do a few more operations with Binary Heap.

🕑

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) — 下面几页会讨论细节。现在试试 Hard Case - O(N) 用相同的输入数组 A=[1,2,3,4,5,6,7] 并且上一页那样观察(不是生成最多次调换的那个)这个版本要比 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...

Bubble Sort
Merge Sort
Insertion Sort
Selection 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() 的时间复杂度很明显是O(K log N),复杂度取决于输出的大小。
🕑
现在你已经到了最大二叉堆基础知识这章的结尾,我们希望你可以在探索模式中探索更多。
然而我们还有一些更有趣的最大二叉堆的挑战,这些在这章节列出。

当你全部学会了的时候,我们邀请你学习更高级的算法,它们用优先队做底层数据结构(之一),例如 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 (默认是最小优先队). 然而这些内置的实现不一定适合我们高效的做一些优先队的扩展操作(因为NUS课程的原因,这里不谈细节)

Python有heapq,但是速度非常慢。OCaml没有内置的优先队列,但是我们可以用另一节课会提到的另一个数据结构来代替。

PS: 堆排序很可能会在 C++ STL 的 partial_sort用到


尽管如此,这里有我们的实现 BinaryHeapDemo.cpp.

🕑
如果你想了解更多关于这个数据结构的有趣问题,你可以去这里做一些训练和测试 二叉堆 (不需要登录)。
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 =

随机

Worst Case: Sorted Ascending

A =

执行

最佳情况:倒排序

N =

随机

Worst Case: Diagonal Entry

v =

执行

1x (一次
)

K =

Kx (PartialSort (部分排序))

Nx (堆排序)

i =
newv =

执行

i =

执行

We use cookies to improve our website.
By clicking ACCEPT, you agree to our use of Google Analytics for analysing user behaviour and improving user experience as described in our Privacy Policy.
By clicking reject, only cookies necessary for site functions will be used.

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

关于

Initially conceived in 2011 by Dr. Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

id, kr, vn, th.

团队

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

本科生研究人员 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

最后一年项目/ UROP学生 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

本科生研究人员 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学生 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

最后一年项目/ UROP学生 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

最后一年项目/ UROP学生 5 (Aug 2021-Dec 2022)
Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

最后一年项目/ UROP学生 6 (Aug 2022-Apr 2023)
Lim Dewen Aloysius, Ting Xiao

最后一年项目/ UROP学生 7 (Aug 2023-Apr 2024)
TBA1, TBA2, TBA3

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

致谢
The birth of this project was made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

使用条款

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors. You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website (https://visualgo.net) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

隐私政策

Version 1.1 (Updated Fri, 14 Jan 2022).

Disclosure to all visitors: We currently use Google Analytics to get an overview understanding of our site visitors. We now give option for user to Accept or Reject this tracker.

Since Wed, 22 Dec 2021, only National University of Singapore (NUS) staffs/students and approved CS lecturers outside of NUS who have written a request to Steven can login to VisuAlgo, anyone else in the world will have to use VisuAlgo as an anonymous user that is not really trackable other than what are tracked by Google Analytics.

For NUS students enrolled in courses that uses VisuAlgo: By using a VisuAlgo account (a tuple of NUS official email address, NUS official student name as in the class roster, and a password that is encrypted on the server side — no other personal data is stored), you are giving a consent for your course lecturer to keep track of your e-lecture slides reading and online quiz training progresses that is needed to run the course smoothly. Your VisuAlgo account will also be needed for taking NUS official VisuAlgo Online Quizzes and thus passing your account credentials to another person to do the Online Quiz on your behalf constitutes an academic offense. Your user account will be purged after the conclusion of the course unless you choose to keep your account (OPT-IN). Access to the full VisuAlgo database (with encrypted passwords) is limited to Steven himself.

For other NUS students, you can self-register a VisuAlgo account by yourself (OPT-IN).

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will be tracked similarly as a normal NUS student account above but it will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.