

from collections import Counter
from functools import total_ordering

from data_structures.heap.heap import Heap

@total_ordering
class   __UpperCamelCase      :




	def __init__(						self		:  str						,		lowerCAmelCase		:  str						,		lowerCAmelCase		:  int							):


		'''simple docstring'''







		UpperCAmelCase_    			=     word
		UpperCAmelCase_    			=     count




	def __eq__(						self		:  Optional[int]						,		lowerCAmelCase		:  object							):


		'''simple docstring'''







		if not isinstance(_lowerCamelCase						,		_lowerCamelCase							):
			return NotImplemented
		return self.count == other.count




	def __lt__(						self		:  Optional[Any]						,		lowerCAmelCase		:  object							):


		'''simple docstring'''







		if not isinstance(_lowerCamelCase						,		_lowerCamelCase							):
			return NotImplemented
		return self.count < other.count



def  __lowerCAmelCase (  A    ,       A      ):
	UpperCAmelCase_    			=     Heap()
	UpperCAmelCase_    			=     Counter(__UpperCamelCase      )
	heap.build_max_heap(
	    [WordCount(__UpperCamelCase    ,       __UpperCamelCase      ) for word, count in count_by_word.items()]      )
	return [heap.extract_max().word for _ in range(min(__UpperCamelCase    ,       len(__UpperCamelCase      )      )      )]


if __name__ == "__main__":
				import doctest

				doctest.testmod()


def  __lowerCAmelCase (  A      ):
	UpperCAmelCase_    			=     len(A      )

	# Set the gap value to be decreased by a factor of 1.3
	# after each iteration
	UpperCAmelCase_    			=     1.3

	# Continue sorting until the gap is 1
	while gap > 1:
		# Decrease the gap value
		UpperCAmelCase_    			=     int(gap / shrink      )

		# Sort the elements using insertion sort
		for i in range(A    ,       len(A      )      ):
			UpperCAmelCase_    			=     collection[i]
			UpperCAmelCase_    			=     i
			while j >= gap and collection[j - gap] > temp:
				UpperCAmelCase_    			=     collection[j - gap]
				j -= gap
			UpperCAmelCase_    			=     temp

	return collection


if __name__ == "__main__":
				import doctest

				doctest.testmod()