A Software Engineering Space

The Heapsort algorithm

Ahh, Heaps.  Heaps are one of those data structures that turn up everywhere. They serve a humble purpose: find the maximum value (depending on if you’re using min or max ordering) of a set efficiently. It is this very purpose that imbues them with the ability to implement a very simple, efficient sorting algorithm. To […]

Randomized Meldable Heaps: An alternative tree structure for the implementation of priority queue

Randomized Meldable Heaps When it comes to priority queues, the binary heap is the go-to data structure when it comes to implementation, and with good reason. Binary heaps offer worst-case logarithmic complexity for all operations that it supports. Despite its popularity, it does have some draw backs. The upheap/downheap operations that drive binary heaps while […]

To search: Linear search and binary searching algorithms

Fundamental Use Once upon a time, most computer time was spent on sorting, and the majority of the rest on searching. I’d say thats probably close to true today, as even browsing the web is, at its most basic an act of searching. Seeing as i’ve covered the sorting side of things, I thought i’d […]

Implementing “foreach” for custom containers

Foreach The “foreach” loop is a special case of the for loop, usually enacted on a linear container such as an array or a list, where for every iteration of the loop, some action is performed on a member of the container until that action has been performed on every element in the collection. Some […]