Advanced Data Structure

Posted on Edited on In ,

Fenwick Tree

Fenwick tree is also called Binary Indexed Tree. This kind of data structure can do the calculation of sum from 0 to ith of a list very efficiently.

It can also be used to calculate the frequency. Below is a code used to calculate the number of values from 0 to i. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class fenwickTree:
    def __init__(n):
        self.array = [0] * n

    def add(i):
        while i < len(self.array):
            self.array[i] += 1
            i += i & -i

    def query(i):
        ans = 0
        while i >= 0:
            ans += self.array[i]
            i -= i & -i
        return ans

Relevant application is in Leetcode No.315.

Heap

Heap is a useful data structure which can store the elements in order. In Python, there is a built in heap library called Heapq.

No.253 - Meeting Room

  • Make the start time of meeting in order
  • Use heap to store the end time of each meeting
  • When the meeting with earliest end time is smaller than the coming meeting with earliest start time, pop that meeting, otherwise not. Then heappush the new end time of the new coming meeting.