Heap implementation in Swift

Hello everyone,

As you can see, I haven’t been blogging for more than three years. That is a long time. But ¬†I had my reasons. A lot has happened in both my personal, and professional life that kept me too busy and sparing little time to focus on blogging. However, I think it is time to start writing again. I like to write about technical topics. So I restart my blogging by kicking it off with this small post, and small snippet of code.

I love the heap data structure. It is a nifty little DS that maintains items in an order, giving you O(1) access to the min/max item, and pops/inserts new items in O(lgN) time. The same structure is used to implement a priority queue, which has uses in many places, e.g. Dijkstra algorithm. So keeping with my habit of implementing a known data structure in short period of free time, I give you a quick implementation of heap written in Swift. Let me know what you think of it, or if you find any problems in it.

Thank you for checking out my blog. I would love to hear from you in the comments section. And lets hope I come up with good content for you to read in the future.

Book Review: Effective Objective-C 2.0 by Matt Galloway

I love reading technical books. They provide you with a broader picture on a topic and go in depth on different issues that online tutorials just simply skim. That’s why each month I pick up a book related to the platforms I work with. My last month’s pick was “Effective Objective-C 2.0” by Matt Galloway. It was an enlightening read, so I thought I would share a review with my blog readers.


If you are like me, you picked Objective-C as a language while learning iOS development. I have over the years picked and improved my know-how of the language that is Objective-C, while being a full time iOS developer. The problem with learning Obj-C as you learn iOS development is that you are for the most part learning only higher level Cocoa (Touch) APIs and hardly get to see the efficient implementation behind these APIs on the language level. Thus I think it is important to set aside sometime, give Cocoa a break, and play with Obj-C language itself and get to know how it works under the hood, many of the new improvements it has to offer since 2.0 version, and some of the new ways the new Apple compiler, LLVM, has improved on it.

“Effective Objective-C 2.0” provides you with a clear path to knowing your programming language. It is divided into 52 items touching different parts of the language, divided into seven chapters.

Chapter 1: Accustoming Yourself to Objective-C

A simple start to the book, introducing you to Objective-C’s roots, how headers import work and how to effectively use it. Also touches on literal syntax, macros, and enumerations.

Chapter 2: Objects, Messaging, and the Runtime

Many newcomers to the language will go a long way working with Cocoa touch without realising that Objective-C has a very powerful runtime whose power can be harnessed to perform many useful tricks. This chapter talks about properties, objects equality, associating custom data to existing classes during runtime, talks about objc_msgSend and how message forwarding works. It also touches upon the very powerful Obj-C runtime feature of method swizzling.

Chapter 3: Interface and API Design

This chapter talks about how to properly implement your classes with clear and useful interfaces.

Chapter 4: Protocols and Categories

Protocols and Categories are prevalent throughout the Cocoa framework. This chapter talks about effectively using categories to provide additional functionality on top of your classes.

Chapter 5: Memory Management

Many people think that after introduction of ARC, studying memory management on iOS is not important. Nothing can be far from the truth. Understanding how memory management works on the platform is essential to understanding how ARC works and to avoid some of the gotchas ARC can have if you don’t understand how to avoid retain cycles even when ARC is enabled.

Chapter 6: Blocks and Grand Central Dispatch

One of the modern features of Obj-C are Blocks. This chapter talks about how to effectively use blocks. It also talks about the C API to handle concurrency on platform namely GCD and compares it to Operation Queues. It talks about how one can use GCD to allow thread synchronisation, instead of the @synthesize construct that most of us are used to.

Chapter 7: The System Frameworks

Last chapter talks about features provided in system frameworks and when should they be preferred. For example using block enumerations to for loops, using toll free bridging for memory management, using NSCache instead of NSDictionary to avail caching etc.


This is a great book to have read. It will certainly make you more aware of what goes under the hood when you use any of the system libraries, and put you in a better position to write better classes of your own and debug like a pro.

UIView bounds vs. frame

New comers to iOS development usually get confused by a UIView having two different properties to represent its position and size. Namely ‘bounds’ and ‘frame’. Surprisingly, many senior iOS devs can’t explain in clear terms the difference between the two either. So I thought I would try to explain in simpler words the difference between the two.

UIView — An infinite sheet:

An instance of UIView always has a height, and a width. But to clearly understand the difference between bounds and frame, we first need to revisit our visualisation of a UIView instance. Think of a UIView as an infinite sheet, that is divided into four quadrants, just like a cartesian coordinate plane. However, a regular cartesian coordinate plane has its y-axes increasing towards the top. While our UIView plane’s y-axes increases downwards, and has negative values upwards. Just like a regular cartesian plane, our UIView plane has its centre at point (0, 0).

Even though a UIView can be thought of as infinite sheet, and we can add subviews to it anywhere in this infinite space, we only get to see a finite section of this infinite sheet at a given time. And this is where bounds and frame come into play.


Bounds define a finite window into the infinite sheet of UIView. At any given time, we only see the contents of the view that lie within the bounds of this view. Any content that is part of the view, but lying outside the bounds won’t appear (or would appear if it is within the bounds of the superview and view doesn’t have its clipsToBounds set to YES, but won’t receive touches). If we change the position and size of bounds to move to another portion of the infinite sheet of view, content at that location would start to appear.

Thus, bounds is a window into an infinite sheet of content that is UIView.


Frame is the location and size of a UIView instance within its superview. Thus if we don’t change frame, but change bounds, view would show different contents, but at the same location within the superview. If we change frame, and keep bounds the same, view would show the same content but at a different location within the superview.

Remember that frame and bounds have same size values, but their origin values can differ.


Bounds is view’s location and size within its own coordinate system. Frame is views location and size within superview’s coordinate system.


SKHeap; A quick MaxHeap and HeapSort implementation

Heap is an interesting data structure. It is a binary tree, that keeps the maximum (in case of MaxHeap) element at the root, thus providing access to it in O(1) i.e. constant time. You can pop the root element in O(lgN) time, and insert new elements into the heap in O(lgN) time as well. Initial buildup of the heap takes linear time. You can sort a sequence of elements using heap, by first building the heap out of all the elements, and then retrieve the elements back. Since initial build up is linear time, each retrieval of the maximum element is O(lgN) time, and you do N such retrievals, the resulting sorting algorithm is of O(NlgN) complexity and called HeapSort.

It is fun to implement these well known data structures and algorithms. So while I was bored and free for half an hour, I quickly wrote a basic implementation of a Heap and HeapSort in Objective-C and pushed it to Github. Check it out and let me know if you like it or find any issues with it.

Topcoder SRM 584; A late correct solution is better than a quick but wrong one

This was an interesting SRM. I solved both easy and medium lightening fast, and moved on to solve the hard one. I understood the hard problem, but just couldn’t come up with a generic solution. So mid way into the problem, I decided to look back at the medium problem to confirm I didn’t miss any corner case. I tested it with a tricky case that I came up with while I was devising the algorithm, but hadn’t tested my solution on after I passed example test cases. Guess what!? It failed!! Bummer. I quickly looked through my solution to cater for this tricky case and resubmitted. That reduced my score for the problem to half of my first submission. But it did save me from a completely failed solution. ;)

DIV2 Medium; Egalitarianism:

If there are any two people in the kingdom that aren’t connected either directly or through some friends, answer is -1. Reason is, there aren’t any limitations imposed between the difference of these two people, and their difference can be arbitrarily large or small.

In the other case, every citizen is connected to every other citizen either directly or through other friends. In such a case, we need to find the maximum friendship distance between any two people, and multiply that with “d”, as that will be the maximum possible difference between their wealth.

We can use Floyd-Warshall algorithm for finding out minimum distance between any two citizens, and then chose the maximum out of these minimum. If maximum is equal to infinity, it means there are two people not connected, so return -1. Otherwise return maximum*d.

A corner case to check for though is that we must not consider a connection to self. If there is a loop in the graph, this loop can have the maximum distance, but we are looking for maximum wealth difference between two different people. This is the case my first implementation missed. Though I did use it in the challenge phase to get +75 points. :)

DIV2 Easy; TopFox:

We can easily generate all possible handles as the constraints are low, and figure out the count of unique ones.


I am back to division 1. Cool!

Topcoder SRM 583; Depressing

I can safely say I knew correct solutions to all of the three problems in this SRM. I solved easy problem lightening fast. Medium was an implementation problem, with quite a few corner cases, but nothing too tricky. It took me a good amount of time, so that I had little time for hard problem. I knew hard problem was finding maximum cost from each point, to any other point, and returning minimum of it. But I couldn’t implement it in time.

That’s not it though. My medium failed. With one of the most stupidest mistakes ever. I was indexing an array of mine with an input that was 1-indexed, while my array was 0-indexed. All I had to do was to subtract 1 from the input before passing it to array as an index, and my solution passes. :(

DIV2-Easy; SwappingDigits:

All we need to do is swap digits at each pair of indices into the string, and see if it produces minimum integer with no leading 0.

DIV2-Medium; IDNumberVerification:

An implementation problem. Check that each part of the ID is valid, and then return gender of the person.


Sad SRM. But meh! Happens.

Codeforces round 186; The one that got rated

We finally had a codeforces round that went smooth and rated. :) Past two rounds that I participated in, both had something going wrong with it, and ended up unrated.

DIV-2 Problem A; Ilya and Bank Account:

You are given an integer N, and you are allowed to drop its last digit, or second last digit, to create an integer with greater value. If N is greater then 0, dropping allowed digits can not increase its value. If it is smaller then 0, dropping one of the allowed digit will give you the largest possible integer.

DIV2 Problem B; Ilya and Queries:

First, iterate over the array, calculating positions where s[i]==s[i+1]. Lets call this new array dp. Then dp[0] = 0. For i=1 to s.size()-1, dp[i] = dp[i-1] if s[i]!=s[i-1], or else dp[i] = dp[i-1]+1. Now to find out count of all the integers ‘i’ between [l, r), such that s[i] = s[i+1], we can simply use dp[r]-d[l].

DIV2 Problem C; Ilya and Matrix:

We want to place all of the 4^n integers in the matrix in such a way, that the beauty of matrix is maximised. Beauty of matrix depends on the highest integer within it, plus the beauty of matrices that we get once we divide given matrix into four square matrices. One of these matrices will get our original highest integer that existed in the bigger matrix this smaller matrix is part of. In order to maximise beauty of the remaining three, it makes sense to place the next three highest integers out of our original 4^n integers in them. In the next step, we will have 16 sub matrices, and in order to maximise beauty of each, it would make sense that all of those 16 have the 16 highest integers from within the 4^n integers. And so on. Thus we iterate over sorted array of our 4^n integers, n times, each time adding first  4^i (where i is iteration number) integers from the array into our result.

DIV2 Problem D; Ilya and Roads:

This was a nice dynamic programming problem. Though I couldn’t figure correct recurrence for it. If someone has a simple explanation for it, please comment.


I got a +140 in rating. Yay!