binaryHeap.py

''' mbinary
#########################################################################
# File : binaryHeap.py
# Author: mbinary
# Mail: zhuheqin1@gmail.com
# Blog: https://mbinary.xyz
# Github: https://github.com/mbinary
# Created Time: 2018-05-19  23:06
# Description:
#########################################################################
'''


from collections import Iterable


class node:
    def __init__(self, val, freq=1):
        self.val = val
        self.freq = freq

    def __eq__(self, a):
        return self.val == a.val

    def __lt__(self, a):
        return self.val < a.val

    def __le__(self, a):
        return self.val <= a.val

    def __gt__(self, a):
        return self.val > a.val

    def __ge__(self, a):
        return self.val >= a.val

    def __ne__(self, a):
        return not self == a


class binaryHeap:
    def __init__(self, s=None, sortByFrequency=False, reverse=False):
        self.sortByFrequency = sortByFrequency
        self.reverse = reverse
        self.data = [node(0)]  # make index begin with 1
        if s == None:
            return
        if not isinstance(s, Iterable):
            s = [s]
        for i in s:
            self.insert(i)

    def __bool__(self):
        return len(self) != 1

    def _cmp(self, a, b):
        if self.sortByFrequency:
            if self.reverse:
                return a.freq > b.freq
            else:
                return a.freq < b.freq
        else:
            if self.reverse:
                return a > b
            else:
                return a < b

    def insert(self, k):
        if not isinstance(k, node):
            k = node(k)
        for j in range(self.data[0].val):
            i = self.data[j+1]
            if i == k:
                i.freq += 1
                if self.sortByFrequency:
                    idx = self.percolateDown(j+1)
                    self.percolateUp(idx)
                return
        self.data.append(k)
        self.data[0].val += 1
        self.percolateUp()

    def percolateUp(self, n=None):
        if n == None:
            n = self.data[0].val
        tmp = self.data[n]
        while n != 1 and self._cmp(tmp, self.data[n//2]):
            self.data[n] = self.data[n//2]
            n = n//2
        self.data[n] = tmp

    def deleteTop(self):
        tmp = self.data[1]
        i = self.percolateDown(1)
        self.data[i] = self.data[-1]
        self.data[0].val -= 1
        del self.data[-1]
        return tmp

    def percolateDown(self, i):
        tmp = self.data[i]
        while self.data[0].val >= 2*i+1:
            if self._cmp(self.data[i*2], self.data[2*i+1]):
                self.data[i] = self.data[2*i]
                i = 2*i
            else:
                self.data[i] = self.data[2*i+1]
                i = 2*i+1
        self.data[i] = tmp
        return i

    def __len__(self):
        return self.data[0].val

    def Nth(self, n=1):
        tmp = []
        for i in range(n):
            tmp.append(self.deleteTop())
        for i in tmp:
            self.insert(i)
        return tmp[-1]

    def display(self):
        val = self.data[0].val+1
        if self.sortByFrequency:
            info = 'heapSort by Frequency:'
        else:
            info = 'heapSort by Value:'
        if self.reverse:
            info += ' From big to small'
        else:
            info += ' From small to big'
        print('*'*15)
        print(info)
        print('total items:%d\nval\tfreq' % (val-1))
        fmt = '{}\t{}'
        for i in range(1, val):
            print(fmt.format(self.data[i].val, self.data[i].freq))
        print('*'*15)


class Test:
    def topKFrequent(self, words, k):
        hp = binaryHeap(sortByFrequency=True, reverse=True)
        for i in words:
            hp.insert(i)
        hp.display()
        n = len(hp)
        mp = {}
        while hp:
            top = hp.deleteTop()
            if top.freq in mp:
                mp[top.freq].append(top.val)
            else:
                mp[top.freq] = [top.val]
        for i in mp:
            mp[i].sort()
        key = sorted(mp.keys(), reverse=True)
        rst = []
        count = 0
        for i in key:
            for j in mp[i]:
                rst.append(j)
                count += 1
                if count == k:
                    return rst


if __name__ == '__main__':
    s = ["plpaboutit", "jnoqzdute", "sfvkdqf", "mjc", "nkpllqzjzp", "foqqenbey", "ssnanizsav", "nkpllqzjzp", "sfvkdqf", "isnjmy", "pnqsz", "hhqpvvt", "fvvdtpnzx", "jkqonvenhx", "cyxwlef", "hhqpvvt", "fvvdtpnzx", "plpaboutit", "sfvkdqf", "mjc", "fvvdtpnzx", "bwumsj", "foqqenbey", "isnjmy", "nkpllqzjzp", "hhqpvvt", "foqqenbey", "fvvdtpnzx", "bwumsj", "hhqpvvt", "fvvdtpnzx", "jkqonvenhx", "jnoqzdute", "foqqenbey", "jnoqzdute", "foqqenbey", "hhqpvvt", "ssnanizsav", "mjc", "foqqenbey", "bwumsj", "ssnanizsav", "fvvdtpnzx", "nkpllqzjzp",
         "jkqonvenhx", "hhqpvvt", "mjc", "isnjmy", "bwumsj", "pnqsz", "hhqpvvt", "nkpllqzjzp", "jnoqzdute", "pnqsz", "nkpllqzjzp", "jnoqzdute", "foqqenbey", "nkpllqzjzp", "hhqpvvt", "fvvdtpnzx", "plpaboutit", "jnoqzdute", "sfvkdqf", "fvvdtpnzx", "jkqonvenhx", "jnoqzdute", "nkpllqzjzp", "jnoqzdute", "fvvdtpnzx", "jkqonvenhx", "hhqpvvt", "isnjmy", "jkqonvenhx", "ssnanizsav", "jnoqzdute", "jkqonvenhx", "fvvdtpnzx", "hhqpvvt", "bwumsj", "nkpllqzjzp", "bwumsj", "jkqonvenhx", "jnoqzdute", "pnqsz", "foqqenbey", "sfvkdqf", "sfvkdqf"]
    test = Test()
    print(test.topKFrequent(s, 5))