堆数据结构基础与常用字符串处理算法实战

堆数据结构基础与常用字符串处理算法实战

一、堆数据结构基础

堆（Heap）本质上是一种特殊的完全二叉树，根据节点大小关系可分为最大堆和最小堆。在最大堆中，父节点始终大于或等于子节点；最小堆则相反。这种结构天然适合实现优先队列。

1. 数组映射关系

堆通常使用数组存储。对于下标为 i 的节点：

• 左子节点下标：2 * i + 1
• 右子节点下标：2 * i + 2
• 父节点下标：(i - 1) / 2

2. 核心操作实现

插入与删除

插入新元素时，将其置于末尾并执行上浮（heapify-up）操作恢复堆序；删除堆顶时，将末尾元素移至顶部并下沉（heapify-down）。

下面是一个最大堆的 C++ 完整实现，包含建堆、插入及打印功能：

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

class MaxHeap {
private:
    vector<int> heap;

    // 上浮操作
    void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        if (index > 0 && heap[index] > heap[parent]) {
            swap(heap[index], heap[parent]);
            heapifyUp(parent);
        }
    }

    // 下沉操作
    void heapifyDown(int index) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int size = heap.size();

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int extractMax() {
        if (heap.empty()) throw out_of_range("Heap is empty");
        int max = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) heapifyDown(0);
        return max;
    }

    void buildHeap(const vector<int>& array) {
        heap = array;
        for (int i = heap.size() / 2 - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    void printHeap() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }
};

堆排序

堆排序利用建堆后堆顶即为最大值的特点，反复取出堆顶并调整剩余部分。时间复杂度 O(nlogn)，空间复杂度 O(1)。

void heapSort(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--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void heapify(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) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

二、字符串处理算法

1. 有效的字母异位词

判断两个字符串是否包含相同字符且频次一致。思路是统计字符频次差值，若全为零则为异位词。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        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;
    }
};

解析：这里用了一个小技巧，遍历一次同时增减计数，最后检查数组即可。空间上固定为 26，属于 O(1)。

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, end = s.size() / 2;
        int count1 = 0, 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;
}

注意：使用 getline 才能读取含空格的整行输入，rfind 从右向左搜索更高效。

4. 验证回文串

只考虑字母数字，忽略大小写，使用双指针向中间靠拢。

class Solution {
public:
    bool isPalindrome(string s) {
        int begin = 0, 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;
    }
};

解析：关键是跳过非有效字符后再比较。如果直接比较可能会因为标点符号导致误判。

三、堆相关选择题解析

题目 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

解析：堆需满足完全二叉树性质且父子节点有序。

• A 项中 53 < 72，不满足最大堆；
• B 项中 53 < 72，不满足最大堆；
• C 项中 16 < 53，不满足最大堆，也不满足最小堆；
• D 项 16 < 31, 16 < 23, 31 < 94, 31 < 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/60, 20<45/40, 60<70/95, 45<50/80，全部满足。 答案：A

题目 3

已知大根堆 25, 13, 10, 12, 9，尾部插入 18，调整过程中比较次数？ 解析：插入 18 后位置在索引 5。父节点为索引 2 (值 10)。18 > 10，交换。新父节点为索引 0 (值 25)。18 < 25，停止。共比较 2 次。 答案：B

题目 4

小根堆 5,8,12,19,28,20,15,22 插入 3，调整后结果？ 解析：3 插入末尾，依次上浮：3 < 19 (换), 3 < 8 (换), 3 < 5 (换)。最终 3 在根节点，原 5 下沉至其左子节点位置。 答案：A

题目 5

堆排序中建堆的时间复杂度？ 解析：虽然单次下沉是 O(logn)，但大部分节点靠近底部，下沉距离短。数学推导证明总复杂度为 O(n)。 答案：A

总结

堆通过数组模拟完全二叉树，实现了高效的优先级管理。掌握上浮下沉机制是理解优先队列的关键。字符串处理方面，哈希计数与双指针是解决频次与对称性问题的利器。实际编码时注意边界条件与字符转换细节，能避免不少潜在 Bug。