<commit_before>from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import numpy as np


def parent(i):
    return i // 2

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1


class MaxPriorityQueue(object):
    """Max Priority Queue."""
    def __init__(self):
        self.heap_ls = [0]
        self.heap_size = 0

    def show(self):
        print(self.heap_ls)

    def max_heapify(self, i):
        l = left(i)
        r = right(r)

        if l <= self.heap_size and self.heap_ls[l] > self.heap_ls[i]:
            max_i = l
        if r <= self.heap_size and self.heap_ls[r] > self.heap_ls[max_i]:
            max_i = r
        if max_i != i:
            self.heap_ls[i], self.heap_ls[max_i] = (
                self.heap_ls[max_i], self.heap_ls[i])
            self.max_heapify(max_i)

    def find_max(self):
        return self.heap_ls[1]

    def extract_max(self):
        if self.heap_size < 1:
            raise ValueError('Heap underflow.')
        maximum = self.heap_ls[1]
        self.heap_ls[1] = self.heap_ls[self.heap_size]
        self.max_heapify(1)
        return maximum

    def increase_key(self, i, key):
        if key < self.heap_ls[i]:
            raise ValueError('New key is smaller than current key.')
        self.heap_ls[i] = key
        while i > 1 and self.heap_ls[parent(i)] < self.heap_ls[i]:
            self.heap_ls[i], self.heap_ls[parent(i)] = (
                self.heap_ls[parent(i)], self.heap_ls[i])
            i = parent(i)

    def insert(self, key):
        self.heap_size += 1
        self.heap_ls.append(-np.inf)
        self.increase_key(self.heap_size, key)


def main():
    max_pq = MaxPriorityQueue()

    # Insert sequentially [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
    print('Insert 16')
    max_pq.insert(16)
    max_pq.show()

    print('Insert 14')
    max_pq.insert(14)
    max_pq.show()

    print('Insert 10')
    max_pq.insert(10)
    max_pq.show()

    print('Insert 8')
    max_pq.insert(8)
    max_pq.show()

    print('Insert 7')
    max_pq.insert(7)
    max_pq.show()

    print('Insert 9')
    max_pq.insert(9)
    max_pq.show()

    print('Insert 3')
    max_pq.insert(3)
    max_pq.show()

    print('Insert 2')
    max_pq.insert(2)
    max_pq.show()

    print('Insert 4')
    max_pq.insert(4)
    max_pq.show()

    print('Insert 1')
    max_pq.insert(1)
    max_pq.show()

    # Increase key 4 at position 9 to 15.
    print('Increase key 4 at position 9 to 15.')
    max_pq.increase_key(9, 15)
    max_pq.show()


if __name__ == '__main__':
    main()
<commit_msg>Revise by micmicking min priority queue<commit_after>from __future__ import absolute_import
from __future__ import division
from __future__ import print_function

import numpy as np


def parent(i):
    return i // 2

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1


class MaxPriorityQueue(object):
    """Max Priority Queue."""
    def __init__(self):
        self.heap_ls = [0]
        self.heap_size = 0

    def show(self):
        print(self.heap_ls)

    def max_heapify(self, i):
        l = left(i)
        r = right(i)
        if l <= self.heap_size and self.heap_ls[l] > self.heap_ls[i]:
            max_i = l
        else:
            max_i = i
        if r <= self.heap_size and self.heap_ls[r] > self.heap_ls[max_i]:
            max_i = r
        if max_i != i:
            self.heap_ls[i], self.heap_ls[max_i] = (
                self.heap_ls[max_i], self.heap_ls[i])
            self.max_heapify(max_i)

    def find_max(self):
        return self.heap_ls[1]

    def extract_max(self):
        if self.heap_size < 1:
            raise ValueError('Heap underflow.')
        maximum = self.heap_ls[1]
        self.heap_ls[1] = self.heap_ls.pop()
        self.heap_size -= 1
        self.max_heapify(1)
        return maximum

    def increase_key(self, i, key):
        if key < self.heap_ls[i]:
            raise ValueError('New key is smaller than current key.')
        self.heap_ls[i] = key
        while i > 1 and self.heap_ls[parent(i)] < self.heap_ls[i]:
            self.heap_ls[i], self.heap_ls[parent(i)] = (
                self.heap_ls[parent(i)], self.heap_ls[i])
            i = parent(i)

    def insert(self, key):
        self.heap_size += 1
        self.heap_ls.append(-np.inf)
        self.increase_key(self.heap_size, key)


def main():
    max_pq = MaxPriorityQueue()

    print('Insert sequentially 5, 7, 3, 1')
    max_pq.insert(5)
    max_pq.insert(7)
    max_pq.insert(3)
    max_pq.insert(1)
    max_pq.show()

    print('Increase key 1 at position 4 to 6.')
    max_pq.increase_key(4, 6)
    max_pq.show()

    print('Find max:')
    print(max_pq.find_max())

    print('Extract max:')
    _max = max_pq.extract_max()
    print(_max)
    print('The remaining:')
    max_pq.show()

if __name__ == '__main__':
    main()

{'fraction_non_alphanumeric': 0.12804254448762528, 'fraction_numerical': 0.01840867253016977, 'mean_word_length': 2.1712062256809337, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4114261', 'n_tokens_mistral': 1891, 'n_tokens_neox': 1748, 'n_words': 396}