- Courses
- Programming
- Heaps And Maps
- Heap And Map Implementation Details

C does not have support for treemaps being a very basic language. You might have to implement your own version of balanced BST. We suggest you take a look at C++ as well. After all, everything C also works in C++.

C++ Standard Template Library provides maps and sets which are implemented > internally using balanced red black trees. We explore maps here for now, although set is very much similar.

```
map<int, int> A; // O(1) declaration which declares an empty tree map.
```

```
A[K] = V; // O(log n). Note that we expect key K to be unique here. If you have keys that will repeat, take a look at multimaps.
```

```
A.erase(K); // O(log n)
```

```
A.find(K) != A.end() // O(log n)
```

```
A[K] // O(log n)
```

```
(A.begin())->first // O(1)
```

```
(A.rbegin())->first // O(1)
```

```
for (map<int,int>::iterator it = A.begin(); it != A.end(); ++it) {
// it->first has the key, it->second has the value.
}
```

```
(A.upper_bound(x))->first // O(log n). Do need to handle the case when x is more than or equal to the max key in the map.
```

```
(A.lower_bound(x))->first // O(log n). Do need to handle the case when x is more than the max key in the map.
```

```
A.size()
```

Java has TreeMap which is very similar to C++ map. Also implemented using Red Black trees.

```
TreeMap<Integer, Integer> A = new TreeMap<Integer, Integer>(); // O(1) declaration which declares an empty tree map.
```

```
A.put(K, V); // Note that we expect key K to be unique here. If you have keys that will repeat, they will be replaced.
// O(log n)
```

```
A.remove(K); // O(log n)
```

```
A.containsKey(K) // O(log n)
```

```
A.get(K) // O(log n)
```

```
A.firstKey() OR A.firstEntry().getKey() // O(1)
```

```
A.lastKey() OR A.lastEntry().getKey() // O(1)
```

```
for (Map.Entry<Integer, Integer> entry : A.entrySet()) {
// entry.getKey() has the key, entry.getValue() has the value
}
```

```
A.ceilingEntry(x).getKey() // O(log n). Do need to handle the case when x is more than the max key in the map.
```

```
A.floorEntry(x).getKey() // O(log n). Do need to handle the case when x is smaller than min key in the map
```

```
A.size()
```

Python does not have a implementation of treemap in standard library ( Sorry python users ). The closes we come to it is with heapq which is implementation of heaps ( http://en.wikipedia.org/wiki/Heap_%28data_structure%29 ) which obviously means that we are restricted in terms of number of things we can do as compared to treemap.

```
A = []; # declares an empty list / heap. O(1)
# Note that heaps are internally implemented using lists for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k.
```

```
heapq.heappush(A, (K, V)); // O(log n)
```

```
heapq.heappop(A)[0]
```

```
A[0][0]
```

```
len(A)
```