Monthly Archives: November 2014

Binary heap

Data structures,

Binary heap is a tree-like data structure that generally can be separated into two types: min-heap and max-heap. The difference is that in the max-heap all nodes are greater than or equal to each of it’s children. In the min-heap everything is vise versa, all nodes are less than or equal to each of its children. Thus, the highest (max-heap) or lowest (min-heap) element is always on the top and this is the main advantage which provides possibility to access the min or the max element in constant time. Another important property is that all levels, except the last last one, must be full.

heap

The last level can be either full or not, but all new elements always added to the last level, from the left to the right.
Continue reading Binary heap →

Hash table

Data structures, ,

Hash table allows you to keep a list of key/value pairs, where each key associated with particular value. Such data structures implement abstract data type which is called either a dictionary, a map, or associative array. As an example from a real life, you can think of phonebook:

phonebookIn the phonebook a person name can be considered as a key, by which we can find a phone number.
Continue reading Hash table →

Deque

Data structures

Deque or double-ended queue is almost the same as the queue. But, the main difference is that it provides possibility to add and remove elements from both sides of the queue. In other words it combines FIFO and LIFO principles.

deque

Double-ended queues are not heavily used in practice, but they can be useful in such task, as browser history. Let say, the browser history must contain last 10 visited URL’s. To do that we can add every visited URL to the front of the deque. Once, we are going to add 11th URL we remove URL from the back.
Continue reading Deque →