import heapq

# 創(chuàng)建堆
data = [5, 7, 9, 1, 3]
heapq.heapify(data)  # 線性時間建堆

# 添加元素
heapq.heappush(data, 4)

# 彈出最小值
min_val = heapq.heappop(data)

# 獲取Top N
largest = heapq.nlargest(3, data)
smallest = heapq.nsmallest(3, data)

class MinHeap:
    """最小堆實現(xiàn)"""
    
    def __init__(self):
        self.heap = []
    
    def push(self, item):
        """添加元素"""
        heapq.heappush(self.heap, item)
    
    def pop(self):
        """彈出最小值"""
        return heapq.heappop(self.heap)
    
    def pushpop(self, item):
        """添加并彈出最小值"""
        return heapq.heappushpop(self.heap, item)
    
    def replace(self, item):
        """彈出最小值并添加新元素"""
        return heapq.heapreplace(self.heap, item)
    
    def top_k(self, k):
        """獲取最小的k個元素"""
        return heapq.nsmallest(k, self.heap)
    
    def __len__(self):
        return len(self.heap)

# 使用示例
heap = MinHeap()
for num in [10, 2, 8, 5, 3]:
    heap.push(num)
print(f"最小3個元素: {heap.top_k(3)}")  # [2, 3, 5]

import random

def quickselect(arr, k):
    """快速選擇算法 - 查找第k小的元素"""
    if len(arr) == 1:
        return arr[0]
    
    pivot = random.choice(arr)
    lows = [x for x in arr if x < pivot]
    highs = [x for x in arr if x > pivot]
    pivots = [x for x in arr if x == pivot]
    
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

def top_k(arr, k):
    """獲取最小的k個元素"""
    kth_smallest = quickselect(arr, k-1)
    return sorted([x for x in arr if x <= kth_smallest])[:k]

# 使用示例
data = [random.randint(1, 1000) for _ in range(1000000)]
top_100 = top_k(data, 100)
print(f"最小的100個數(shù): {top_100[:10]}...")

def distributed_top_k(data, k, chunk_size=1000000):
    """分布式Top K查找"""
    chunks = [data[i:i+chunk_size] for i in range(0, len(data), chunk_size)]
    
    # 第一階段：每個分塊找到Top K
    chunk_top_k = []
    for chunk in chunks:
        heapq.heapify(chunk)
        chunk_top_k.append(heapq.nsmallest(k, chunk))
    
    # 第二階段：合并所有分塊的Top K
    merged = []
    for top in chunk_top_k:
        merged.extend(top)
    
    heapq.heapify(merged)
    return heapq.nsmallest(k, merged)

# 10億數(shù)據(jù)查找Top 100
big_data = [random.random() for _ in range(10**9)]
top_100 = distributed_top_k(big_data, 100)

from concurrent.futures import ProcessPoolExecutor

def parallel_top_k(data, k, workers=8):
    """并行Top K查找"""
    chunk_size = len(data) // workers
    chunks = [data[i*chunk_size:(i+1)*chunk_size] for i in range(workers)]
    
    with ProcessPoolExecutor(max_workers=workers) as executor:
        # 并行處理每個分塊
        futures = [executor.submit(heapq.nsmallest, k, chunk) for chunk in chunks]
        
        # 收集結(jié)果
        results = []
        for future in futures:
            results.extend(future.result())
    
    # 合并結(jié)果
    return heapq.nsmallest(k, results)

# 使用示例
import numpy as np
large_data = np.random.uniform(0, 100, 100000000)  # 1億個隨機(jī)數(shù)
top_100 = parallel_top_k(large_data, 100, workers=8)

class Product:
    def __init__(self, id, name, price, sales):
        self.id = id
        self.name = name
        self.price = price
        self.sales = sales
    
    def __repr__(self):
        return f"{self.name} (￥{self.price}, 銷量:{self.sales})"

# 創(chuàng)建產(chǎn)品列表
products = [
    Product(1, "iPhone 15", 8999, 12000),
    Product(2, "iPad Pro", 6999, 8500),
    Product(3, "MacBook Air", 10999, 6500),
    Product(4, "Apple Watch", 2999, 15000),
    Product(5, "AirPods Pro", 1999, 28000)
]

# 查找最暢銷的3個產(chǎn)品
top_selling = heapq.nlargest(3, products, key=lambda p: p.sales)
print("最暢銷產(chǎn)品:")
for p in top_selling:
    print(f"- {p}")

# 查找最貴的2個產(chǎn)品
most_expensive = heapq.nlargest(2, products, key=lambda p: p.price)
print("\n最貴產(chǎn)品:")
for p in most_expensive:
    print(f"- {p}")

def top_k_complex(items, k, key_func):
    """多條件Top K查找"""
    # 創(chuàng)建堆
    heap = []
    for item in items:
        # 計算排序鍵
        key = key_func(item)
        
        # 維護(hù)大小為k的堆
        if len(heap) < k:
            heapq.heappush(heap, (key, item))
        elif key > heap[0][0]:
            heapq.heapreplace(heap, (key, item))
    
    # 提取結(jié)果
    return [item for _, item in sorted(heap, reverse=True)]

# 使用示例：查找性價比最高的產(chǎn)品（銷量/價格）
best_value = top_k_complex(
    products, 
    k=3, 
    key_func=lambda p: p.sales / p.price
)

print("\n性價比最高產(chǎn)品:")
for p in best_value:
    value = p.sales / p.price
    print(f"- {p.name}: ￥{p.price}, 銷量:{p.sales}, 性價比:{value:.2f}")

class StreamingTopK:
    """實時Top K維護(hù)系統(tǒng)"""
    
    def __init__(self, k):
        self.k = k
        self.heap = []  # 最小堆維護(hù)當(dāng)前Top K
    
    def add(self, item, value):
        """添加新元素"""
        # 使用負(fù)值構(gòu)建最小堆模擬最大堆
        entry = (-value, item)
        
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, entry)
        elif entry > self.heap[0]:
            heapq.heapreplace(self.heap, entry)
    
    def get_top_k(self):
        """獲取當(dāng)前Top K"""
        return [item for value, item in sorted(self.heap, reverse=True)]

# 使用示例
stream_processor = StreamingTopK(k=3)

# 模擬數(shù)據(jù)流
data_stream = [
    ("A", 15), ("B", 20), ("C", 10), 
    ("D", 25), ("E", 18), ("F", 30)
]

for item, value in data_stream:
    stream_processor.add(item, value)
    print(f"添加 {item}={value} 后Top 3: {stream_processor.get_top_k()}")

from collections import deque
import heapq
import time

class TimeWindowTopK:
    """時間窗口Top K維護(hù)"""
    
    def __init__(self, k, window_size):
        """
        :param k: Top K數(shù)量
        :param window_size: 時間窗口大?。耄?
        """
        self.k = k
        self.window_size = window_size
        self.data = deque()  # (timestamp, value, data)
        self.heap = []       # 當(dāng)前Top K
    
    def add(self, value, data):
        """添加新數(shù)據(jù)點(diǎn)"""
        now = time.time()
        self.data.append((now, value, data))
        
        # 維護(hù)時間窗口
        while self.data and now - self.data[0][0] > self.window_size:
            self.data.popleft()
        
        # 重建堆
        self._rebuild_heap()
    
    def _rebuild_heap(self):
        """重建Top K堆"""
        self.heap = []
        for timestamp, value, data in self.data:
            if len(self.heap) < self.k:
                heapq.heappush(self.heap, (value, data))
            elif value > self.heap[0][0]:
                heapq.heapreplace(self.heap, (value, data))
    
    def get_top_k(self):
        """獲取當(dāng)前Top K"""
        return sorted(self.heap, reverse=True)

# 使用示例
window_topk = TimeWindowTopK(k=3, window_size=10)

# 添加數(shù)據(jù)
window_topk.add(15, "Event A")
time.sleep(1)
window_topk.add(20, "Event B")
time.sleep(1)
window_topk.add(10, "Event C")
print(f"當(dāng)前Top 3: {window_topk.get_top_k()}")

# 添加新數(shù)據(jù)
time.sleep(3)
window_topk.add(25, "Event D")
print(f"添加后Top 3: {window_topk.get_top_k()}")

# 等待窗口滑動
time.sleep(8)
print(f"窗口滑動后Top 3: {window_topk.get_top_k()}")

class StockAnalyzer:
    """股票交易分析系統(tǒng)"""
    
    def __init__(self, k=10):
        self.top_gainers = []  # 最大漲幅
        self.top_losers = []   # 最大跌幅
        self.top_volume = []   # 最高交易量
        self.k = k
    
    def process_trades(self, trades):
        """處理交易數(shù)據(jù)"""
        for trade in trades:
            # 計算漲跌幅
            change = (trade['price'] - trade['prev_close']) / trade['prev_close'] * 100
            
            # 更新最大漲幅
            self._update_heap(self.top_gainers, change, trade, max_heap=True)
            
            # 更新最大跌幅
            self._update_heap(self.top_losers, -change, trade, max_heap=True)
            
            # 更新最高交易量
            self._update_heap(self.top_volume, trade['volume'], trade, max_heap=True)
    
    def _update_heap(self, heap, value, data, max_heap=True):
        """更新堆狀態(tài)"""
        # 使用負(fù)值轉(zhuǎn)換最大堆為最小堆
        key = value if max_heap else -value
        entry = (key, data)
        
        if len(heap) < self.k:
            heapq.heappush(heap, entry)
        elif key > heap[0][0]:
            heapq.heapreplace(heap, entry)
    
    def get_top_gainers(self):
        """獲取漲幅最大的股票"""
        return [data for _, data in sorted(self.top_gainers, reverse=True)]
    
    def get_top_losers(self):
        """獲取跌幅最大的股票"""
        return [data for _, data in sorted(self.top_losers, reverse=True)]
    
    def get_top_volume(self):
        """獲取交易量最大的股票"""
        return [data for _, data in sorted(self.top_volume, reverse=True)]

# 使用示例
trades = [
    {'symbol': 'AAPL', 'price': 185.5, 'prev_close': 182.3, 'volume': 1000000},
    {'symbol': 'MSFT', 'price': 340.2, 'prev_close': 345.6, 'volume': 850000},
    {'symbol': 'GOOGL', 'price': 135.7, 'prev_close': 132.5, 'volume': 1200000},
    # ...更多交易數(shù)據(jù)
]

analyzer = StockAnalyzer(k=5)
analyzer.process_trades(trades)

print("漲幅Top 5:")
for stock in analyzer.get_top_gainers():
    print(f"{stock['symbol']}: {stock['price']}")

print("\n交易量Top 5:")
for stock in analyzer.get_top_volume():
    print(f"{stock['symbol']}: {stock['volume']}")

class RecommenderSystem:
    """實時推薦系統(tǒng)"""
    
    def __init__(self, k=10):
        self.user_preferences = {}  # 用戶偏好向量
        self.item_features = {}     # 物品特征向量
        self.k = k
    
    def update_user_preference(self, user_id, item_id, rating):
        """更新用戶偏好"""
        if user_id not in self.user_preferences:
            self.user_preferences[user_id] = {}
        self.user_preferences[user_id][item_id] = rating
    
    def update_item_features(self, item_id, features):
        """更新物品特征"""
        self.item_features[item_id] = features
    
    def recommend(self, user_id, n=10):
        """為用戶生成推薦"""
        if user_id not in self.user_preferences:
            return []
        
        # 獲取用戶評分過的物品
        user_ratings = self.user_preferences[user_id]
        
        # 計算未評分物品的預(yù)測評分
        scores = []
        for item_id, features in self.item_features.items():
            if item_id not in user_ratings:
                # 簡化計算：實際中應(yīng)使用更復(fù)雜的預(yù)測模型
                score = sum(
                    user_ratings.get(other_item, 0) * self._similarity(features, self.item_features[other_item])
                    for other_item in user_ratings
                )
                scores.append((score, item_id))
        
        # 獲取Top N推薦
        return heapq.nlargest(n, scores, key=lambda x: x[0])
    
    def _similarity(self, features1, features2):
        """計算特征相似度（簡化版）"""
        # 實際應(yīng)用中應(yīng)使用余弦相似度等
        return sum(a * b for a, b in zip(features1, features2))

# 使用示例
recommender = RecommenderSystem()

# 添加物品特征
recommender.update_item_features("item1", [0.8, 0.2, 0.5])
recommender.update_item_features("item2", [0.6, 0.3, 0.7])
# ...添加更多物品

# 更新用戶評分
recommender.update_user_preference("user1", "item1", 5)
recommender.update_user_preference("user1", "item2", 4)
# ...添加更多評分

# 生成推薦
recommendations = recommender.recommend("user1", n=5)
print("推薦物品:")
for score, item_id in recommendations:
    print(f"- {item_id} (預(yù)測評分: {score:.2f})")

class LogAnalyzer:
    """日志分析系統(tǒng)"""
    
    def __init__(self, k=10):
        self.error_counter = {}  # 錯誤計數(shù)
        self.slow_requests = []  # 慢請求
        self.k = k
    
    def process_log(self, log_entry):
        """處理日志條目"""
        # 錯誤日志統(tǒng)計
        if log_entry['level'] == 'ERROR':
            error_type = log_entry['error_type']
            self.error_counter[error_type] = self.error_counter.get(error_type, 0) + 1
        
        # 慢請求記錄
        if 'response_time' in log_entry and log_entry['response_time'] > 1000:
            self._update_heap(
                self.slow_requests, 
                log_entry['response_time'], 
                log_entry
            )
    
    def _update_heap(self, heap, value, data):
        """更新堆狀態(tài)"""
        entry = (value, data)
        if len(heap) < self.k:
            heapq.heappush(heap, entry)
        elif value > heap[0][0]:
            heapq.heapreplace(heap, entry)
    
    def top_errors(self, k=None):
        """獲取Top K錯誤類型"""
        k = k or self.k
        return heapq.nlargest(k, self.error_counter.items(), key=lambda x: x[1])
    
    def top_slow_requests(self, k=None):
        """獲取Top K慢請求"""
        k = k or self.k
        return heapq.nlargest(k, self.slow_requests, key=lambda x: x[0])

# 使用示例
logs = [
    {'level': 'INFO', 'message': 'Request received'},
    {'level': 'ERROR', 'error_type': 'Timeout', 'message': 'Request timeout'},
    {'level': 'ERROR', 'error_type': 'DBError', 'message': 'Database connection failed'},
    {'level': 'INFO', 'response_time': 1200, 'endpoint': '/api/users'},
    # ...更多日志
]

analyzer = LogAnalyzer(k=5)
for log in logs:
    analyzer.process_log(log)

print("Top 5錯誤類型:")
for error, count in analyzer.top_errors():
    print(f"- {error}: {count}次")

print("\nTop 5慢請求:")
for time, log in analyzer.top_slow_requests():
    print(f"- {log['endpoint']}: {time}ms")

def memory_efficient_top_k(data, k, chunk_size=1000000):
    """內(nèi)存優(yōu)化的Top K查找"""
    # 初始化堆
    heap = []
    
    # 分塊處理
    for i in range(0, len(data), chunk_size):
        chunk = data[i:i+chunk_size]
        
        # 處理當(dāng)前分塊
        for value in chunk:
            if len(heap) < k:
                heapq.heappush(heap, value)
            elif value > heap[0]:
                heapq.heapreplace(heap, value)
    
    return sorted(heap, reverse=True)

# 使用示例：處理10億數(shù)據(jù)只需O(k)內(nèi)存
big_data = (random.random() for _ in range(10**9))  # 生成器表達(dá)式減少內(nèi)存
top_100 = memory_efficient_top_k(big_data, 100)

class MultiIndexTopK:
    """多維度Top K索引系統(tǒng)"""
    
    def __init__(self, k=10):
        self.k = k
        self.heaps = {
            'price': [],   # 價格最高
            'sales': [],   # 銷量最高
            'rating': []   # 評分最高
        }
        self.data = {}     # 存儲完整數(shù)據(jù)
    
    def add_item(self, item_id, price, sales, rating):
        """添加商品"""
        self.data[item_id] = {'price': price, 'sales': sales, 'rating': rating}
        
        # 更新各維度堆
        self._update_heap('price', price, item_id)
        self._update_heap('sales', sales, item_id)
        self._update_heap('rating', rating, item_id)
    
    def _update_heap(self, dimension, value, item_id):
        """更新指定維度堆"""
        heap = self.heaps[dimension]
        entry = (value, item_id)
        
        if len(heap) < self.k:
            heapq.heappush(heap, entry)
        elif value > heap[0][0]:
            heapq.heapreplace(heap, entry)
    
    def get_top_k(self, dimension):
        """獲取指定維度Top K"""
        return sorted(self.heaps[dimension], reverse=True)

# 使用示例
index = MultiIndexTopK(k=3)
index.add_item("A", price=100, sales=500, rating=4.5)
index.add_item("B", price=200, sales=300, rating=4.8)
index.add_item("C", price=150, sales=400, rating=4.2)
index.add_item("D", price=250, sales=200, rating=4.9)

print("價格Top 3:")
for price, item_id in index.get_top_k('price'):
    print(f"- {item_id}: ￥{price}")

print("\n銷量Top 3:")
for sales, item_id in index.get_top_k('sales'):
    print(f"- {item_id}: {sales}件")