第六十六天

口述堆排序的原理?

堆排序是一种基于完全二叉树特性的比较排序算法，它的基本原理如下：

1. 构建初始堆：

   • 首先，堆排序将待排序的序列看作是一个完全二叉树（通常以数组形式存储），其中每个节点的值都与其子节点满足某种顺序关系。
   • 根据要求排序的方向，可以选择构建大顶堆（降序排列）或小顶堆（升序排列）。对于降序排列，要求每个节点的值都不小于其任意子节点的值，即大顶堆的性质是“父节点 >= 子节点”。

2. 调整堆：

   • 从最后一个非叶子节点开始（通常是最后一个元素的父节点），逐层向上进行下沉操作（sift down），直至整个数组成为一个合法的大顶堆。下沉操作确保每个节点都满足堆的性质。

3. 交换堆顶元素和末尾元素：

   • 当堆构建完成后，堆顶元素（即整个序列的最大值或最小值，取决于是否是大顶堆或小顶堆）与数组末尾的元素交换位置，即将最大（或最小）值放置在了正确的位置上。

4. 缩小堆范围并重新调整：

   • 将堆的有效范围减小1，忽略已经排好序的最后一个元素，对剩下的n-1个元素重新调整成一个堆。

5. 重复过程：

   • 重复上述步骤，每次都将当前堆顶的最大（或最小）元素放到正确的位置上，并重新调整剩余元素构成新的堆。

6. 终止条件：

   • 当堆的大小减小至1时，所有元素都已经有序，排序完成。

通过这种方式，堆排序可以在O(n log n)的时间复杂度内完成排序，因为它构建堆的过程需O(n)时间，而交换堆顶元素并重新调整堆的过程共需进行n-1次，每次调整的时间复杂度大致为O(log n)，故总时间复杂度为O(n log n)。堆排序是一种原地排序算法，不需要额外的空间来存储数据。

聊天系统如何直到客户是否在线? 用户聊天使用的是长连接还是短连接?使用websocket连接, 还需要自己实现心跳保活吗?

不需要, websocket自己已经实现了心跳保活机制, 只需要设置pingInterval和pingTimeout即可