设计一个消息优先级排序算法，比如系统消息优先级最高，好友消息次之，群消息再次，请说明如何用数据结构（如优先队列）实现，以及如何处理并发更新时的冲突。

1) 【一句话结论】
核心是通过优先队列存储带唯一ID和时间戳的消息元数据，结合类型权重（系统100、好友80、群60）与时间戳倒序计算优先级，用细粒度锁处理并发更新，实现高效优先级排序。

2) 【原理/概念讲解】
消息优先级排序需明确消息元数据结构：每个消息对象包含唯一ID（避免重复处理）、类型（系统/好友/群）、时间戳（作为优先级tie - breaker）和计算优先级。优先级计算公式为：优先级 = 类型权重 + 时间戳倒序值（类型权重固定，时间戳越大（最新）优先级越高）。优先队列（二叉堆）按此优先级排序，插入时计算优先级并加入队列。并发场景下，多线程操作队列时用细粒度锁（如消息锁或队列锁）保证操作原子性，避免数据冲突。类比：优先队列像急诊系统，系统消息（急诊）优先级最高，时间戳新（刚到）的消息优先级更高，队列中优先级高的先处理。

3) 【对比与适用场景】

方案	数据结构	并发控制	适用场景	注意点
优先队列+细粒度锁	二叉堆	细粒度锁（如消息锁）	高并发、频繁插入/更新	锁粒度小，性能较好，但实现复杂
优先队列+互斥锁	二叉堆	全局互斥锁	低中并发，简单实现	串行化，可能影响性能
优先队列+无锁（CAS）	二叉堆（支持CAS）	CAS操作	低中并发，需高吞吐	可能导致ABA问题，需处理
哈希表+优先队列	哈希表+二叉堆	互斥锁	查询消息时快速定位	查询效率高，插入依赖队列

4) 【示例】

class Message:
    def __init__(self, id, type_, timestamp):
        self.id = id          # 唯一ID
        self.type_ = type_    # 0: system, 1: friend, 2: group
        self.timestamp = timestamp
        self.priority = self._calculate_priority()

    def _calculate_priority(self):
        weight_map = {0: 100, 1: 80, 2: 60}  # 类型权重
        # 时间戳倒序（时间越大优先级越高）
        return weight_map[self.type_] + self.timestamp

class MessagePriorityQueue:
    def __init__(self):
        self.heap = []
        self.lock = threading.Lock()  # 并发控制锁

    def push(self, message):
        with self.lock:
            self.heap.append(message)
            self._sift_up(len(self.heap) - 1)

    def pop(self):
        with self.lock:
            if not self.heap:
                return None
            top = self.heap[0]
            last = self.heap.pop()
            if self.heap:
                self.heap[0] = last
                self._sift_down(0)
            return top

    def _sift_up(self, index):
        parent = (index - 1) // 2
        if index > 0 and self.heap[parent].priority > self.heap[index].priority:
            self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
            self._sift_up(parent)

    def _sift_down(self, index):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        if left < len(self.heap) and self.heap[left].priority < self.heap[smallest].priority:
            smallest = left
        if right < len(self.heap) and self.heap[right].priority < self.heap[smallest].priority:
            smallest = right
        if smallest != index:
            self.heap[smallest], self.heap[index] = self.heap[index], self.heap[smallest]
            self._sift_down(smallest)

# 使用示例（假设并发场景）
queue = MessagePriorityQueue()
msg1 = Message(1, 0, 0)  # 系统消息
msg2 = Message(2, 1, 0)  # 好友消息
msg3 = Message(3, 2, 0)  # 群消息
queue.push(msg1)
queue.push(msg2)
queue.push(msg3)
print(queue.pop().id)  # 输出1（系统消息优先级最高）

5) 【面试口播版答案】
面试官您好，设计消息优先级排序，核心是用优先队列存储带唯一ID和时间戳的消息元数据，通过类型权重（系统100、好友80、群60）与时间戳倒序计算优先级，用细粒度锁处理并发更新。具体来说，每个消息对象计算优先级后插入二叉堆，队列按优先级排序，新消息插入时获取锁，计算优先级后入队，这样保证最高优先级消息先处理。比如系统消息优先级100+最新时间戳，好友80+次新时间戳，队列中系统消息总在顶部，处理时优先弹出。并发场景下，多个线程插入时，锁确保队列状态一致，避免数据冲突。总结就是优先队列结合消息元数据，用锁处理并发，实现高效优先级排序。

6) 【追问清单】

• 问：如果消息优先级需要动态调整怎么办？
  答：给消息对象增加优先级字段，用户设置后更新值，重新计算优先级并调整队列位置（如堆调整或重新插入）。
• 问：优先队列的插入和删除时间复杂度如何？
  答：二叉堆的插入和删除是O(log n)，适合消息数量较多的情况。
• 问：并发时如果多个线程同时调用pop，会不会有问题？
  答：pop操作需锁，保证每次只有一个线程弹出消息，避免竞争条件。
• 问：数据结构选择为什么用二叉堆而不是平衡树？
  答：二叉堆实现简单，插入和删除的堆调整操作时间复杂度低，适合优先级排序场景。

7) 【常见坑/雷区】

• 优先级反转：若低优先级消息阻塞高优先级，需处理（本题类型固定，风险低，但需说明动态调整时可能的问题）。
• 锁粒度选择：全局锁影响性能，细粒度锁提升效率但实现复杂，需权衡。
• 优先级定义错误：系统消息优先级设为最低会导致排序错误，需明确映射关系。
• 消息元数据缺失：若缺少唯一ID或时间戳，可能导致重复处理，需包含标识。
• 并发控制不当：无锁CAS可能遇到ABA问题，导致优先级错误，通常用锁更稳妥。