




import warnings

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from sklearn.metrics import pairwise_distances

warnings.filterwarnings('ignore')

lowercase_     :    List[Any]      =			'K-MEANS-CLUST/ '


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_     ,   snake_case_=None						):

						'''simple docstring'''


						if seed is not None:  # useful for obtaining consistent results
												np.random.seed(_a						)
						_UpperCAmelCase													=					data.shape[0]  # number of data points

						# Pick K indices from range [0, N).
						_UpperCAmelCase													=					np.random.randint(0     ,   _a     ,   _a						)

						# Keep centroids as dense format, as many entries will be nonzero due to averaging.
						# As long as at least one document in a cluster contains a word,
						# it will carry a nonzero weight in the TF-IDF vector of the centroid.
						_UpperCAmelCase													=					data[rand_indices, :]

						return centroids


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_						):

						'''simple docstring'''


						return pairwise_distances(_a     ,   _a     ,   metric="euclidean"						)


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_						):

						'''simple docstring'''


						_UpperCAmelCase													=					centroid_pairwise_dist(_a     ,   _a						)

						# Compute cluster assignments for each data point:
						# Fill in the blank (RHS only)
						_UpperCAmelCase													=					np.argmin(_a     ,   axis=1						)

						return cluster_assignment


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_     ,   snake_case_						):

						'''simple docstring'''


						_UpperCAmelCase													=					[]
						for i in range(_a						):
												# Select all data points that belong to cluster i. Fill in the blank (RHS only)
												_UpperCAmelCase													=					data[cluster_assignment == i]
												# Compute the mean of the data points. Fill in the blank (RHS only)
												_UpperCAmelCase													=					member_data_points.mean(axis=0						)
												new_centroids.append(_a						)
						_UpperCAmelCase													=					np.array(_a						)

						return new_centroids


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_     ,   snake_case_     ,   snake_case_						):

						'''simple docstring'''


						_UpperCAmelCase													=					0.0
						for i in range(_a						):
												# Select all data points that belong to cluster i. Fill in the blank (RHS only)
												_UpperCAmelCase													=					data[cluster_assignment == i, :]

												if member_data_points.shape[0] > 0:  # check if i-th cluster is non-empty
																		# Compute distances from centroid to data points (RHS only)
																		_UpperCAmelCase													=					pairwise_distances(
																		    _a     ,   [centroids[i]]     ,   metric="euclidean"						)
																		_UpperCAmelCase													=					distances**2
																		heterogeneity += np.sum(_a						)

						return heterogeneity


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_						):

						'''simple docstring'''


						plt.figure(figsize=(7, 4)						)
						plt.plot(_a     ,   linewidth=4						)
						plt.xlabel("# Iterations"						)
						plt.ylabel("Heterogeneity"						)
						plt.title(f"""Heterogeneity of clustering over time, K={k:d}"""						)
						plt.rcParams.update({"font.size": 16}						)
						plt.show()


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_     ,   snake_case_     ,   snake_case_=500     ,   snake_case_=None     ,   snake_case_=False						):

						'''simple docstring'''


						_UpperCAmelCase													=					initial_centroids[:]
						_UpperCAmelCase													=					None

						for itr in range(_a						):
												if verbose:
																		print(_a     ,   end=""						)

												# 1. Make cluster assignments using nearest centroids
												_UpperCAmelCase													=					assign_clusters(_a     ,   _a						)

												# 2. Compute a new centroid for each of the k clusters, averaging all data
												#    points assigned to that cluster.
												_UpperCAmelCase													=					revise_centroids(_a     ,   _a     ,   _a						)

												# Check for convergence: if none of the assignments changed, stop
												if (
												    prev_cluster_assignment is not None
												    and (prev_cluster_assignment == cluster_assignment).all()
												):
																		break

												# Print number of new assignments
												if prev_cluster_assignment is not None:
																		_UpperCAmelCase													=					np.sum(prev_cluster_assignment != cluster_assignment						)
																		if verbose:
																								print(
																								    f"""    {num_changed:5d} elements changed their cluster assignment."""						)

        # Record heterogeneity convergence metric
												if record_heterogeneity is not None:
																		# YOUR CODE HERE
																		_UpperCAmelCase													=					compute_heterogeneity(_a     ,   _a     ,   _a     ,   _a						)
																		record_heterogeneity.append(_a						)

												_UpperCAmelCase													=					cluster_assignment[:]

						return centroids, cluster_assignment


# Mock test below
if False:  # change to true to run this test case.
				from sklearn import datasets as ds

				lowercase_     :    Optional[int]      =			ds.load_iris()
				lowercase_     :    Dict      =			3
				lowercase_     :    Dict      =			[]
				lowercase_     :    int      =			get_initial_centroids(dataset['data'], k, seed=0)
				lowercase_    ,					lowercase_     :    str      =			kmeans(
				    dataset['data'],
				    k,
				    initial_centroids,
				    maxiter=4_00,
				    record_heterogeneity=heterogeneity,
				    verbose=True,
				)
				plot_heterogeneity(heterogeneity, k)


def 							__SCREAMING_SNAKE_CASE  (      snake_case_     ,   snake_case_     ,   snake_case_=None						):

						'''simple docstring'''


						if fill_missing_report:
												_UpperCAmelCase													=					df.fillna(value=_a						)
						_UpperCAmelCase													=					1
						_UpperCAmelCase													=					df.select_dtypes(np.number						).columns
						_UpperCAmelCase													=					(
						    df.groupby(["Cluster"]						)[  # construct report dataframe
						        numeric_cols
						    ]  # group by cluster number
						    .agg(
						        [
						            ("sum", np.sum),
						            ("mean_with_zeros", lambda snake_case_						: np.mean(np.nan_to_num(_a						)						)),
						            ("mean_without_zeros", lambda snake_case_						: x.replace(0     ,   np.NaN						).mean()),
						            (
						                "mean_25-75",
						                lambda snake_case_						: np.mean(
						                    np.nan_to_num(
						                        sorted(_a						)[
						                            round(len(_a						) * 25 / 100						) : round(len(_a						) * 75 / 100						)
						                        ]						)						),
						            ),
						            ("mean_with_na", np.mean),
						            ("min", lambda snake_case_						: x.min()),
						            ("5%", lambda snake_case_						: x.quantile(0.05						)),
						            ("25%", lambda snake_case_						: x.quantile(0.25						)),
						            ("50%", lambda snake_case_						: x.quantile(0.50						)),
						            ("75%", lambda snake_case_						: x.quantile(0.75						)),
						            ("95%", lambda snake_case_						: x.quantile(0.95						)),
						            ("max", lambda snake_case_						: x.max()),
						            ("count", lambda snake_case_						: x.count()),
						            ("stdev", lambda snake_case_						: x.std()),
						            ("mode", lambda snake_case_						: x.mode()[0]),
						            ("median", lambda snake_case_						: x.median()),
						            ("# > 0", lambda snake_case_						: (x > 0).sum()),
						        ]						)
						    .T.reset_index()
						    .rename(index=_a     ,   columns={"level_0": "Features", "level_1": "Type"}						)
						)  # rename columns
						# calculate the size of cluster(count of clientID's)
						_UpperCAmelCase													=					report[
						    (report["Features"] == "dummy") & (report["Type"] == "count")
						].copy()  # avoid SettingWithCopyWarning
						_UpperCAmelCase													=					(
						    "ClusterSize"  # rename created cluster df to match report column names
						)
						_UpperCAmelCase													=					"# of Customers"
						_UpperCAmelCase													=					pd.DataFrame(
						    clustersize.iloc[:, 2:].values
						    / clustersize.iloc[:, 2:].values.sum()						)
						_UpperCAmelCase													=					"% of Customers"  # rename created cluster df to match report column names
						_UpperCAmelCase													=					"ClusterProportion"
						_UpperCAmelCase													=					clusterproportion.columns.tolist()
						_UpperCAmelCase													=					cols[-2:] + cols[:-2]
						_UpperCAmelCase													=					clusterproportion[cols]  # rearrange columns to match report
						_UpperCAmelCase													=					report.columns
						_UpperCAmelCase													=					pd.DataFrame(
						    abs(
						        report[report["Type"] == "count"].iloc[:, 2:].values
						        - clustersize.iloc[:, 2:].values						)						)  # generating df with count of nan values
						_UpperCAmelCase													=					0
						_UpperCAmelCase													=					"# of nan"
						_UpperCAmelCase													=					report[
						    report["Type"] == "count"
						].Features.tolist()  # filling values in order to match report
						_UpperCAmelCase													=					a.columns.tolist()
						_UpperCAmelCase													=					cols[-2:] + cols[:-2]
						_UpperCAmelCase													=					a[cols]  # rearrange columns to match report
						_UpperCAmelCase													=					report.columns  # rename columns to match report
						_UpperCAmelCase													=					report.drop(
						    report[report.Type == "count"].index						)  # drop count values except cluster size
						_UpperCAmelCase													=					pd.concat(
						    [report, a, clustersize, clusterproportion]     ,   axis=0						)  # concat report with clustert size and nan values
						_UpperCAmelCase													=					report["Features"].isin(_a						)
						_UpperCAmelCase													=					report.columns.tolist()
						_UpperCAmelCase													=					cols[0:2] + cols[-1:] + cols[2:-1]
						_UpperCAmelCase													=					report[cols]
						_UpperCAmelCase													=					{
						    "ClusterSize": 9,
						    "ClusterProportion": 8,
						    "mean_with_zeros": 7,
						    "mean_with_na": 6,
						    "max": 5,
						    "50%": 4,
						    "min": 3,
						    "25%": 2,
						    "75%": 1,
						    "# of nan": 0,
						    "# > 0": -1,
						    "sum_with_na": -2,
						}
						_UpperCAmelCase													=					(
						    report.assign(
						        Sortera=lambda snake_case_						: x.Type.map(_a						)     ,   Sortera=lambda snake_case_						: list(reversed(range(len(_a						)						)						)						)     ,   )
						    .sort_values(["Sorter1", "Mark", "Sorter2"]     ,   ascending=_a						)
						    .drop(["Sorter1", "Sorter2"]     ,   axis=1						)
						)
						_UpperCAmelCase													=					""
						_UpperCAmelCase													=					report.reset_index()
						_UpperCAmelCase													=					report.drop(columns=["index"]						)
						return report


if __name__ == "__main__":
				import doctest

				doctest.testmod()










from __future__ import annotations

from abc import abstractmethod
from collections.abc import Iterable
from typing import Generic, Protocol, TypeVar






class    __lowerCAmelCase			(	UpperCAmelCase__			):







			@abstractmethod
			def __lt__(	self   :      T   ,   snake_case__   :      T				):




									"""simple docstring"""


									pass







			@abstractmethod
			def __gt__(	self   :      T   ,   snake_case__   :      T				):




									"""simple docstring"""


									pass







			@abstractmethod
			def __eq__(	self   :      T   ,   snake_case__   :      object				):




									"""simple docstring"""


									pass




lowercase_     :    Tuple      =			TypeVar('T', bound=Comparable)






class    __lowerCAmelCase			(	Generic[T]			):







			def __init__(	self   :      Optional[int]				):




									"""simple docstring"""


									_UpperCAmelCase													=					[]
									_UpperCAmelCase													=					0







			def __repr__(	self   :      Dict				):




									"""simple docstring"""


									return str(self.h				)







			def UpperCamelCase      (	self   :      Optional[Any]   ,   snake_case__   :      int				):




									"""simple docstring"""


									if child_idx > 0:
															return (child_idx - 1) // 2
									return None







			def UpperCamelCase      (	self   :      Tuple   ,   snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					2 * parent_idx + 1
									if left_child_index < self.heap_size:
															return left_child_index
									return None







			def UpperCamelCase      (	self   :      Union[str, Any]   ,   snake_case__   :      int				):




									"""simple docstring"""


									_UpperCAmelCase													=					2 * parent_idx + 2
									if right_child_index < self.heap_size:
															return right_child_index
									return None







			def UpperCamelCase      (	self   :      Dict   ,   snake_case__   :      int				):




									"""simple docstring"""


									if index < self.heap_size:
															_UpperCAmelCase													=					index
															_UpperCAmelCase													=					self.left_child_idx(snake_case__				)
															_UpperCAmelCase													=					self.right_child_idx(snake_case__				)
															# check which child is larger than its parent
															if left_child is not None and self.h[left_child] > self.h[violation]:
																					_UpperCAmelCase													=					left_child
															if right_child is not None and self.h[right_child] > self.h[violation]:
																					_UpperCAmelCase													=					right_child
															# if violation indeed exists
															if violation != index:
																					# swap to fix the violation
																					_UpperCAmelCase							,			_UpperCAmelCase													=					self.h[index], self.h[violation]
																					# fix the subsequent violation recursively if any
																					self.max_heapify(snake_case__				)







			def UpperCamelCase      (	self   :      Tuple   ,   snake_case__   :      Iterable[T]				):




									"""simple docstring"""


									_UpperCAmelCase													=					list(snake_case__				)
									_UpperCAmelCase													=					len(self.h				)
									if self.heap_size > 1:
															# max_heapify from right to left but exclude leaves (last level)
															for i in range(self.heap_size // 2 - 1   ,   -1   ,   -1				):
																					self.max_heapify(snake_case__				)







			def UpperCamelCase      (	self   :      Tuple				):




									"""simple docstring"""


									if self.heap_size >= 2:
															_UpperCAmelCase													=					self.h[0]
															_UpperCAmelCase													=					self.h.pop(-1				)
															self.heap_size -= 1
															self.max_heapify(0				)
															return me
									elif self.heap_size == 1:
															self.heap_size -= 1
															return self.h.pop(-1				)
									else:
															raise Exception("Empty heap"				)







			def UpperCamelCase      (	self   :      str   ,   snake_case__   :      T				):




									"""simple docstring"""


									self.h.append(snake_case__				)
									_UpperCAmelCase													=					(self.heap_size - 1) // 2
									self.heap_size += 1
									while idx >= 0:
															self.max_heapify(snake_case__				)
															_UpperCAmelCase													=					(idx - 1) // 2







			def UpperCamelCase      (	self   :      Any				):




									"""simple docstring"""


									_UpperCAmelCase													=					self.heap_size
									for j in range(size - 1   ,   0   ,   -1				):
															_UpperCAmelCase							,			_UpperCAmelCase													=					self.h[j], self.h[0]
															self.heap_size -= 1
															self.max_heapify(0				)
									_UpperCAmelCase													=					size


if __name__ == "__main__":
				import doctest

				# run doc test
				doctest.testmod()

				# demo
				for unsorted in [
				    [0],
				    [2],
				    [3, 5],
				    [5, 3],
				    [5, 5],
				    [0, 0, 0, 0],
				    [1, 1, 1, 1],
				    [2, 2, 3, 5],
				    [0, 2, 2, 3, 5],
				    [2, 5, 3, 0, 2, 3, 0, 3],
				    [6, 1, 2, 7, 9, 3, 4, 5, 10, 8],
				    [1_03, 9, 1, 7, 11, 15, 25, 2_01, 2_09, 1_07, 5],
				    [-45, -2, -5],
				]:
								print(f"""unsorted array: {unsorted}""")

								lowercase_     :    Heap[int]      =			Heap()
								heap.build_max_heap(unsorted)
								print(f"""after build heap: {heap}""")

								print(f"""max value: {heap.extract_max()}""")
								print(f"""after max value removed: {heap}""")

								heap.insert(1_00)
								print(f"""after new value 100 inserted: {heap}""")

								heap.heap_sort()
								print(f"""heap-sorted array: {heap}\n""")




