堆数据结构与字符串处理算法详解

堆排序

堆排序利用堆的性质进行排序，主要步骤是构建最大堆，然后反复将堆顶元素移至末尾并调整堆结构。

void heapSort(std::vector<int>& arr) {
    int n = arr.size();
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

堆排序时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

二、字符串处理算法

1. 有效的字母异位词

判断两个字符串是否包含相同的字符且频率一致。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        std::vector<int> char_counts(26, 0);
        for (int i = 0; i < s.length(); ++i) {
            char_counts[s[i] - 'a']++;
            char_counts[t[i] - 'a']--;
        }
        for (auto count : char_counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }
};

思路很简单，用数组统计字符频次差值。遍历完如果全为 0，说明互为异位词。时间复杂度 O(n)。

2. 判断字符串的两半是否相似

给定偶数长度字符串，比较前后两半元音字母数量是否相同。

class Solution {
public:
    bool isVowel(char c) {
        c = tolower(c);
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    bool halvesAreAlike(string s) {
        int begin = 0;
        int count1 = 0;
        int end = s.size() / 2;
        int count2 = 0;

        while (end < s.size()) {
            if (isVowel(s[begin])) count1++;
            if (isVowel(s[end])) count2++;
            begin++; end++;
        }
        return count1 == count2;
    }
};

双指针同步遍历，分别计数即可。

3. 字符串最后一个单词的长度

计算字符串末尾单词长度，需处理空格情况。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    size_t pos = s.rfind(' ');
    if (pos != string::npos) {
        cout << s.size() - pos - 1 << endl;
    } else {
        cout << s.size() << endl;
    }
    return 0;
}

使用 rfind 从后找空格，若找到则计算剩余长度，否则整个串即为单词。

4. 验证回文串

只考虑字母数字，忽略大小写。

class Solution {
public:
    bool isPalindrome(string s) {
        int begin = 0;
        int end = s.size() - 1;
        while (begin < end) {
            while (begin < end && !isalnum(s[begin])) begin++;
            while (begin < end && !isalnum(s[end])) end--;
            if (tolower(s[begin]) != tolower(s[end])) {
                return false;
            }
            begin++; end--;
        }
        return true;
    }
};

双指针向中间靠拢，跳过非有效字符后比较。注意 tolower 转换。

三、堆相关选择题解析

1. 下列哪个关键码序列是一个堆？ A. 94,31,53,23,16,72 B. 94,53,31,72,16,23 C. 16,53,23,94,31,72 D. 16,31,23,94,53,72

解析： 选项 D 对应最小堆结构：根节点 16 小于子节点 31 和 23；31 小于 94 和 53；23 小于 72。满足最小堆性质。 答案：D

2. 将关键字序列 50, 40, 95, 20, 15, 70, 60, 45, 80 调整成一个小根堆，堆结构是 15,20,60,45,40,70, 95,50,80，该说法正确吗？ 解析： 检查父子关系：15<20, 15<60；20<45, 20<40；60<70, 60<95；45<50, 45<80。所有节点均满足小根堆性质。 答案：A

3. 已知序列 25, 13, 10, 12, 9 是大根堆，插入新元素 18，调整为大根堆，比较次数是？ 解析： 插入 18 到末尾，父节点为 10。18>10，交换（第 1 次比较）。新父节点为 25。18<25，停止（第 2 次比较）。 答案：B

4. 已知关键字序列 5,8,12,19, 28, 20, 15,22 是小根堆，插入关键字 3，调整后得到的小根堆是？ 解析： 插入 3 后上浮。3<19 交换，3<8 交换，3<5 交换。最终堆顶为 3，顺序为 3, 5, 12, 8, 28, 20, 15, 22, 19。 答案：A

5. 在堆排序的过程中，建立一个堆的时间复杂度是？ 解析： 虽然单次下沉是 O(logn)，但建堆是从最后一个非叶子节点开始，大部分节点下沉距离很短。数学推导证明总复杂度为 O(n)。 答案：A

掌握堆的底层逻辑和常见字符串技巧，对理解优先队列及面试高频题很有帮助。实际编码时注意边界条件，比如空指针或越界访问。