Recall that heaps are introduced to help illustrate arrays. One important operation on arrays is sorting and heaps can also be leveraged for that purpose. We know that a heap provides us the element with the maximum (or minimum) value on the top. Repeating the heapify operation for the rest of elements would continue telling us the second largest value and so on. This is the basic idea of heapsort.
Heaps are a useful data structure where the element on the top possesses the maximum (for max heap) or minimum (for min heap) value. A heap is essentially a specialized tree with two properties.
One interesting aspect about binary trees is the way to store and represent them. Linked lists provide an intuitive illustration of binary trees, while extra spaces are required for pointers. Arrays seem to enable the most compact representation for binary trees, but the advantage only applies to some cases like complete binary trees.
The reader-writer problem is another synchronization problem of accessing a shared resource between two different roles. The only constraint is that when someone is writing, no others are allowed to either read or write. This indicates that at a time there can be only one active writer or multiple active readers.
The producer-consumer problem is also known as the bounded-buffer problem. It’s about the synchronization between a producer and a consumer who share a bounded buffer. The producer generates and puts items into the buffer, one at a time, and pauses when the buffer is full. The consumer consumes and removes items from the buffer, one at a time, and pauses when the buffer is empty. We can generalize the producer-consumer problem to have multiple producers or consumers.
Processors are often utilized effectively by running multiple tasks simultaneously. To guarantee the correct results of concurrent tasks, synchronization is desired across processes that execute those tasks. The fundamental of synchronization relies on the support of hardware, upon which a wide variety of high-level synchronization operations are built on software.
Social networks play an important role in our daily life. Without physical connections, we are aware of the status of our friends. We are even able to connect with famous persons and learn their life, which was unimaginable before. One key way of connections in social networks is via feeds, where people publish status or information and others who subscribe or follow it would see. With more and more people are connecting virtually, there is a massive growth of feeds and their flow between people. A system to support such function in the global scale is the foundation of modern social networks.
Have you ever wondered how a web page is displayed in the browser once you type an URL and press enter? What happens behind the scene is actually quite complex and interesting, though all of them complete in seconds and thus is usually transparent to users.
The performance a computer system is related to its physical properties. Knowing some of those common performance numbers helps us develop an intuition for the hardware. With that, we are able to evaluate a system design without first building it. It also allows us to think more thoroughly when making decisions for system design.
Can sorting be even faster while we’ve mentioned in the previous article that the upper bound of sorting is O(nlogn)? The answer is yes. We can do sorting in linear time if the data set meets certain conditions.