32：自动排序优先队列：堆排序与决策树优先级计算

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个取出元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    
    return arr

# 测试
arr = [12, 11, 13, 5, 6, 7]
print("排序前:", arr)
heap_sort(arr)
print("排序后:", arr)

class PriorityQueue:
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left(self, i):
        return 2 * i + 1
    
    def right(self, i):
        return 2 * i + 2
    
    def insert(self, item):
        self.heap.append(item)
        i = len(self.heap) - 1
        # 上浮操作
        while i > 0 and self.heap[self.parent(i)] < self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def extract_max(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        # 下沉操作
        self._heapify(0)
        return root
    
    def _heapify(self, i):
        largest = i
        left = self.left(i)
        right = self.right(i)
        
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._heapify(largest)
    
    def peek(self):
        return self.heap[0] if self.heap else None

# 测试
pq = PriorityQueue()
pq.insert(10)
pq.insert(20)
pq.insert(15)
pq.insert(30)
pq.insert(5)

print("堆顶元素:", pq.peek())
print("取出最大元素:", pq.extract_max())
print("堆顶元素:", pq.peek())

class DecisionTreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 特征索引
        self.threshold = threshold  # 阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的值

class DecisionTree:
    def __init__(self, max_depth=None):
        self.max_depth = max_depth
    
    def fit(self, X, y):
        self.n_features_ = len(X[0])
        self.tree_ = self._grow_tree(X, y)
    
    def _grow_tree(self, X, y, depth=0):
        n_samples, n_features = len(X), len(X[0])
        n_labels = len(set(y))
        
        # 终止条件
        if (depth >= self.max_depth or n_labels == 1 or n_samples < 2):
            leaf_value = self._most_common_label(y)
            return DecisionTreeNode(value=leaf_value)
        
        # 选择最佳特征和阈值
        feat_idxs = range(n_features)
        best_feature, best_threshold = self._best_criteria(X, y, feat_idxs)
        
        # 分割数据
        left_idxs, right_idxs = self._split(X[:, best_feature], best_threshold)
        left = self._grow_tree(X[left_idxs, :], y[left_idxs], depth + 1)
        right = self._grow_tree(X[right_idxs, :], y[right_idxs], depth + 1)
        return DecisionTreeNode(best_feature, best_threshold, left, right)
    
    def _best_criteria(self, X, y, feat_idxs):
        best_gain = -1
        split_idx, split_thresh = None, None
        
        for feat_idx in feat_idxs:
            X_column = X[:, feat_idx]
            thresholds = sorted(set(X_column))
            
            for threshold in thresholds:
                gain = self._information_gain(y, X_column, threshold)
                if gain > best_gain:
                    best_gain = gain
                    split_idx = feat_idx
                    split_thresh = threshold
        
        return split_idx, split_thresh
    
    def _information_gain(self, y, X_column, threshold):
        # 计算信息增益
        parent_entropy = self._entropy(y)
        left_idxs, right_idxs = self._split(X_column, threshold)
        
        if len(left_idxs) == 0 or len(right_idxs) == 0:
            return 0
        
        n = len(y)
        n_left, n_right = len(left_idxs), len(right_idxs)
        entropy_left = self._entropy(y[left_idxs])
        entropy_right = self._entropy(y[right_idxs])
        child_entropy = (n_left / n) * entropy_left + (n_right / n) * entropy_right
        
        return parent_entropy - child_entropy
    
    def _split(self, X_column, threshold):
        left_idxs = [i for i, x in enumerate(X_column) if x <= threshold]
        right_idxs = [i for i, x in enumerate(X_column) if x > threshold]
        return left_idxs, right_idxs
    
    def _entropy(self, y):
        hist = np.bincount(y)
        ps = hist / len(y)
        return -np.sum([p * np.log2(p) for p in ps if p > 0])
    
    def _most_common_label(self, y):
        counter = Counter(y)
        return counter.most_common(1)[0][0]
    
    def predict(self, X):
        return [self._traverse_tree(x, self.tree_) for x in X]
    
    def _traverse_tree(self, x, node):
        if node.value is not None:
            return node.value
        
        if x[node.feature] <= node.threshold:
            return self._traverse_tree(x, node.left)
        else:
            return self._traverse_tree(x, node.right)

# 测试
import numpy as np
from collections import Counter

X = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9], [2, 3, 4], [5, 6, 7], [8, 9, 10]])
y = np.array([0, 1, 2, 0, 1, 2])

model = DecisionTree(max_depth=3)
model.fit(X, y)

print("预测结果:", model.predict(np.array([[3, 4, 5], [6, 7, 8]])))

class AutoSortPriorityQueue:
    def __init__(self, decision_tree=None):
        self.priority_queue = PriorityQueue()
        self.decision_tree = decision_tree
    
    def add_task(self, task, features):
        # 使用决策树计算优先级
        if self.decision_tree:
            priority = self.decision_tree.predict([features])[0]
        else:
            # 默认优先级计算
            priority = sum(features)
        
        # 将任务和优先级一起插入优先队列
        self.priority_queue.insert((-priority, task))  # 负号用于实现最大堆
    
    def get_next_task(self):
        if not self.priority_queue.heap:
            return None
        _, task = self.priority_queue.extract_max()
        return task
    
    def peek_next_task(self):
        if not self.priority_queue.heap:
            return None
        _, task = self.priority_queue.peek()
        return task
    
    def size(self):
        return len(self.priority_queue.heap)

# 测试
auto_pq = AutoSortPriorityQueue()
auto_pq.add_task("任务1", [1, 2, 3])
auto_pq.add_task("任务2", [4, 5, 6])
auto_pq.add_task("任务3", [7, 8, 9])

print("下一个任务:", auto_pq.get_next_task())
print("下一个任务:", auto_pq.get_next_task())
print("下一个任务:", auto_pq.get_next_task())