heap_structure_app.py

"""
堆结构应用模块
Heap Structure Application Module
"""

from hash_table_app import HashOptimizedNetwork


class MaxHeap:
    """
    最大堆实现，用于维护Top-K排名
    Max Heap implementation for maintaining Top-K rankings
    """
    
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, value):
        """
        插入元素
        Insert element
        """
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        """
        向上调整堆
        Heapify up
        """
        while i != 0 and self.heap[self.parent(i)][0] < self.heap[i][0]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def extract_max(self):
        """
        提取最大元素
        Extract maximum element
        """
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        
        return root
    
    def _heapify_down(self, i):
        """
        向下调整堆
        Heapify down
        """
        largest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left][0] > self.heap[largest][0]:
            largest = left
        
        if right < len(self.heap) and self.heap[right][0] > self.heap[largest][0]:
            largest = right
        
        if largest != i:
            self.swap(i, largest)
            self._heapify_down(largest)
    
    def peek(self):
        """
        查看堆顶元素
        Peek at root element
        """
        return self.heap[0] if self.heap else None
    
    def size(self):
        """
        返回堆大小
        Return heap size
        """
        return len(self.heap)


class MinHeap:
    """
    最小堆实现，用于维护Top-K排名
    Min Heap implementation for maintaining Top-K rankings
    """
    
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
    
    def insert(self, value):
        """
        插入元素
        Insert element
        """
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)
    
    def _heapify_up(self, i):
        """
        向上调整堆
        Heapify up
        """
        while i != 0 and self.heap[self.parent(i)][0] > self.heap[i][0]:
            self.swap(i, self.parent(i))
            i = self.parent(i)
    
    def extract_min(self):
        """
        提取最小元素
        Extract minimum element
        """
        if not self.heap:
            return None
        
        if len(self.heap) == 1:
            return self.heap.pop()
        
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        
        return root
    
    def _heapify_down(self, i):
        """
        向下调整堆
        Heapify down
        """
        smallest = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left][0] < self.heap[smallest][0]:
            smallest = left
        
        if right < len(self.heap) and self.heap[right][0] < self.heap[smallest][0]:
            smallest = right
        
        if smallest != i:
            self.swap(i, smallest)
            self._heapify_down(smallest)
    
    def peek(self):
        """
        查看堆顶元素
        Peek at root element
        """
        return self.heap[0] if self.heap else None
    
    def size(self):
        """
        返回堆大小
        Return heap size
        """
        return len(self.heap)


def get_top_k_with_heap(data, k, max_heap=True):
    """
    使用堆获取前K个元素
    Get top K elements using heap
    
    Args:
        data (list): 数据列表 Data list
        k (int): 前K个 Top K
        max_heap (bool): 是否使用最大堆 Whether to use max heap
        
    Returns:
        list: 前K个元素列表 List of top K elements
    """
    if max_heap:
        heap = MaxHeap()
    else:
        heap = MinHeap()
    
    for value in data:
        if heap.size() < k:
            heap.insert(value)
        elif max_heap and value[0] > heap.peek()[0]:
            heap.extract_max()
            heap.insert(value)
        elif not max_heap and value[0] < heap.peek()[0]:
            heap.extract_min()
            heap.insert(value)
    
    result = []
    while heap.size() > 0:
        if max_heap:
            result.append(heap.extract_max())
        else:
            result.append(heap.extract_min())
    
    # 如果使用的是最小堆，需要反转结果 If using min heap, reverse the result
    if not max_heap:
        result.reverse()
    
    return result


class HeapOptimizedNetwork(HashOptimizedNetwork):
    """
    使用堆结构优化的社交网络类
    Social Network class optimized with heap structures
    """
    
    def get_top_k_by_followers(self, k):
        """
        获取粉丝数前K名的用户
        Get top K users by number of followers
        
        Args:
            k (int): 前K名 Top K
            
        Returns:
            list: 前K名用户列表 List of top K users
        """
        # 使用最小堆维护Top-K列表
        # Use min heap to maintain Top-K list
        min_heap = MinHeap()
        
        for user_id in range(self.n):
            followers_count = self.user_attributes[user_id]['followers']
            
            if min_heap.size() < k:
                # 堆未满，直接插入 Heap not full, insert directly
                min_heap.insert((followers_count, user_id))
            elif followers_count > min_heap.peek()[0]:
                # 当前用户粉丝数比堆顶多，替换堆顶 Current user has more followers than heap top, replace heap top
                min_heap.extract_min()
                min_heap.insert((followers_count, user_id))
        
        # 提取结果 Extract results
        result = []
        temp_list = []
        
        # 将堆中元素取出并按粉丝数降序排列 Extract elements from heap and sort by followers in descending order
        while min_heap.size() > 0:
            followers_count, user_id = min_heap.extract_min()
            temp_list.append((followers_count, user_id))
        
        # 按粉丝数降序排列 Sort by followers in descending order
        temp_list.sort(reverse=True)
        
        for followers_count, user_id in temp_list:
            result.append((user_id, followers_count))
        
        return result
    
    def get_top_k_by_posts(self, k):
        """
        获取发帖数前K名的用户
        Get top K users by number of posts
        
        Args:
            k (int): 前K名 Top K
            
        Returns:
            list: 前K名用户列表 List of top K users
        """
        # 使用最小堆维护Top-K列表
        # Use min heap to maintain Top-K list
        min_heap = MinHeap()
        
        for user_id in range(self.n):
            posts_count = self.user_attributes[user_id]['posts']
            
            if min_heap.size() < k:
                # 堆未满，直接插入 Heap not full, insert directly
                min_heap.insert((posts_count, user_id))
            elif posts_count > min_heap.peek()[0]:
                # 当前用户发帖数比堆顶多，替换堆顶 Current user has more posts than heap top, replace heap top
                min_heap.extract_min()
                min_heap.insert((posts_count, user_id))
        
        # 提取结果 Extract results
        result = []
        temp_list = []
        
        # 将堆中元素取出并按发帖数降序排列 Extract elements from heap and sort by posts in descending order
        while min_heap.size() > 0:
            posts_count, user_id = min_heap.extract_min()
            temp_list.append((posts_count, user_id))
        
        # 按发帖数降序排列 Sort by posts in descending order
        temp_list.sort(reverse=True)
        
        for posts_count, user_id in temp_list:
            result.append((user_id, posts_count))
        
        return result
    
    def update_user_posts(self, user_id, posts_count):
        """
        更新用户发帖数并更新相关数据结构
        Update user post count and update related data structures
        
        Args:
            user_id (int): 用户ID User ID
            posts_count (int): 新的发帖数 New post count
        """
        if 0 <= user_id < self.n:
            self.user_attributes[user_id]['posts'] = posts_count
            # 更新哈希表 Update hash table
            self.user_info_table.insert(user_id, self.user_attributes[user_id])


# 测试示例
if __name__ == "__main__":
    print("堆结构应用 - 示例运行")
    print("Heap Structure Application - Example Run")
    
    # 创建一个堆优化的网络 Create a heap-optimized network
    network = HeapOptimizedNetwork(10, directed=True, storage_type="adj_list")
    
    # 添加一些边 Add some edges
    edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]
    for u, v in edges:
        network.add_edge(u, v)
    
    # 随机设置一些用户的粉丝数和发帖数 Set random follower and post counts for some users
    import random
    for i in range(10):
        network.user_attributes[i]['followers'] = random.randint(10, 100)
        network.user_attributes[i]['posts'] = random.randint(5, 50)
        network.user_info_table.insert(i, network.user_attributes[i])
    
    print(f"添加了 {len(edges)} 条边并设置了用户属性")
    print(f"Added {len(edges)} edges and set user attributes")
    
    # 获取粉丝数前3的用户 Get top 3 users by followers
    top_followers = network.get_top_k_by_followers(3)
    print(f"\n粉丝数前3的用户: {top_followers}")
    print(f"Top 3 users by followers: {top_followers}")
    
    # 获取发帖数前3的用户 Get top 3 users by posts
    top_posts = network.get_top_k_by_posts(3)
    print(f"发帖数前3的用户: {top_posts}")
    print(f"Top 3 users by posts: {top_posts}")
    
    # 更新某个用户的发帖数 Update a user's post count
    network.update_user_posts(5, 100)
    print(f"\n更新用户5的发帖数为100后，发帖数前3的用户: {network.get_top_k_by_posts(3)}")
    print(f"After updating user 5's post count to 100, top 3 by posts: {network.get_top_k_by_posts(3)}")
    
    # 测试堆的基本操作 Test basic heap operations
    print(f"\n测试堆的基本操作...")
    print(f"Testing basic heap operations...")
    
    # 测试最大堆 Test max heap
    max_heap = MaxHeap()
    values = [(10, 'A'), (20, 'B'), (15, 'C'), (30, 'D'), (25, 'E')]
    for val in values:
        max_heap.insert(val)
    
    print("最大堆内容 (依次提取最大值):")
    print("Max heap content (extract max依次):")
    while max_heap.size() > 0:
        print(f"  {max_heap.extract_max()}")
    
    # 测试最小堆 Test min heap
    min_heap = MinHeap()
    for val in values:
        min_heap.insert(val)
    
    print("\n最小堆内容 (依次提取最小值):")
    print("Min heap content (extract min依次):")
    while min_heap.size() > 0:
        print(f"  {min_heap.extract_min()}")
    
    # 测试获取前K个元素的功能 Test get top K functionality
    print(f"\n测试获取前K个元素的功能...")
    print(f"Testing get top K functionality...")
    
    data = [(10, 'A'), (20, 'B'), (15, 'C'), (30, 'D'), (25, 'E'), (5, 'F'), (35, 'G')]
    top_3_max = get_top_k_with_heap(data, 3, max_heap=True)
    print(f"数据中最大的3个元素: {top_3_max}")
    print(f"Largest 3 elements in data: {top_3_max}")
    
    top_3_min = get_top_k_with_heap(data, 3, max_heap=False)
    print(f"数据中最小的3个元素: {top_3_min}")
    print(f"Smallest 3 elements in data: {top_3_min}")