GT

Putting more thoughts on heap and heapify

In a recent conversation, I was asked what the time complexity of heapify is. I said O(N * Log N) confidently. After putting more thoughts on it, I found it’s not.

I read through the source code of Python3’s builtin lib heapq, which provides a handful of methods such as heapify, heappop and heappush. I found there is a bit more complicated math behind it, and a trade-off that the author made in the implementation.

Just be clear, in this article, heap is binary min-heap.

Read More »



My Summary on Graph Algorithms

In this article, I will summarize the some topics on graph theories and algorithms.

In a nutshell, the topics on graph data structure include: traversal, connectivity, shortest path, minimum spanning tree, topology sorting.

Read More »



Algorithm: Longest Increasing Subsequence

When designing a test case this week, I ran into a problem that related to the length of the “longest increasing subsequence” problem. This is a classical problem in ACM, and there are tons of blog articles and stackoverflow questions about this subject. Most of them are really hard to get, but I’m trying to organize the thought in my own words here.

What’s “Longest Increasing Subsequence” (LIS)?

For example, given an unsorted array:

nums = [7,5,3,6,1,9,12]

The LIS is [5,6,9,12], therefore the length of LIS is 4.

Read More »



Sublime Text 3: Use From Behind a Proxy

The plugin “Package Control” plays the role in Sublime Text as “apt-get” or “yum” in Linux, but it does not come with Sublime Text. We can install it easily by the guide provided by packagecontrol.io.

However, in some certain network environment(e.g. isolated corporate network), accessing everything outside must go through a proxy, and Sublime Text does not use the OS global network proxy preferences. People often get connection timeout when installing the package control by the guide.

Setting up the network proxy inside Sublime Text is outlined in this article.

Read More »