Did I implement this correctly? Segment Tree - Review please


  • 0
    S

    I was asked to find minimum or maximum from a given range in an array of millions of unsorted elements. Elements wont change but query should be efficient. Now I thought of "segment tree" conceptually and implemented this. Is this really a good implementation or answers the question correctly? Of course I couldn't write code like below but conveyed the idea...does this look okay?

    class Node(object):
        def __init__(self,start,end,left=None,right=None):
            self.start = start
            self.end   = end
            self.left  = left
            self.right = right
    
    class SegmentTree(object):
        def __init__(self,nums):
            self.root = None
            self.nums = nums
    
            # append all elements of array and their range in queue
            q = []
            for i in range(len(nums)):
                node = Node(i,i)
                q.append(node)
    
            n = len(nums)
            # if n or number of items is not power of 2
            if ( n & (n-1)) != 0:
                # count nearest power of two greater than n
                i = 1
                while i < n:
                    i <<= 1
                # add dumy nodes to have full binary tree
                for x in range((i-n)):
                    self.nums.append(-sys.maxsize)
                    q.append(Node(n+x,n+x))
    
            # must have at least 2 items in queue to form a parent
            while len(q) > 1:
                # pop first two!
                left = q.pop(0)
                right = q.pop(0)
                # make a root! merge their ranges!
                root = Node(left.start, right.end, left, right)
                q.append(root)
    
            # when only one item in queue, its root!
            self.root = q.pop()
    
        def __findMaxAtRoot(self,root,start,end):
            if root:
                # if either end of range represents a node of tree, return its value
                if root.start == start and root.end == start or root.start == end and root.end == end:
                    return self.nums[root.start]
    
                if root.start <= start <= root.end or root.start <= end <= root.end:
                    # start falls with in a range or end falls with in a range of a node
                    # send query to its children
                    maxl = self.__findMaxAtRoot(root.left,start,end)
                    maxr = self.__findMaxAtRoot(root.right,start,end)
                    return max(maxl,maxr)
            # if range falls outside control of node, return -sys.maxsize
            return -sys.maxsize
    
        def findMax(self,start,end):
            return self.__findMaxAtRoot(self.root,start,end)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.