堆和堆排序

堆排序

堆和优先队列

• 普通队列: 先进先出; 后进后出.
• 优先队列: 出队顺序和入队顺序无关, 和优先级相关.

二叉堆

• 任何一个节点都不大于他的父节点

image

• 二叉堆是一棵完全二叉树

image

用数组存储二叉堆

因为是一棵完全二叉树, 所以可以使用数组存储.

image

依照层序自上而下存储.

image

parent(i) = i/2
left child (i) = 2 * i
right child (2) = 2 * i + 1

堆的 C++ 实现

基本框架

这里使用 C++ 的模板类来实现一个大根堆, 基本框架如下.

template<typename Item>
class MaxHeap {
private:
    Item *data;
    int count;

public:
    MaxHeap(int capacity) {
        data = new Item[capacity + 1];
        count = 0;
    }

    ~MaxHeap() {
        delete[] data;
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;
    }
};

• 使用模板来实现
• 使用 Item 类型的动态数组 data 来存储数据.
• 构造函数中, 传入最大容量 capacity, 我们构建的 data 数组大小为 capacity+1 (因为数组中位置 0 不存数据).
• 相应的析构函数中释放内存空间.
• 定义 size() 函数表示当前存储的数据大小.
• isEmpty() 函数表示当前堆是否为空.

向堆中添加元素

image

向堆中添加元素, 需要使得新元素放在堆中的合适位置. 实现思路也非常简单:

• 首先将新元素放在堆的末尾.
• 比较新元素与其父节点, 如果大于父节点, 则与父节点交换.
• 直到该元素满足要求.

具体实现也非常简单

void insert(Item item) {
  assert(count + 1 <= capacity);
  data[++count] = item;
  shiftUp(count);
}

void shiftUp(int k) {
  // 注意 k > 1, k 最小为 2
    while(k > 1 && arr[k/2] < arr[k]) {
    swap(arr[k/2], arr[k]);
    k /= 2;
  }
}

删除堆中的一个元素 (出队操作)

对于大根堆, 出堆只能移除根元素 (最大的元素). 在移除一个元素后, 还需要保持堆的性质不变, 具体的操作包括以下几个步骤:

• 出队根元素
• 将最后一个元素移动到根元素位置
• ShiftDown 操作

ShiftDown 操作就是将根节点的元素逐渐下移到合适位置的操作, 具体来说就是:

• k 初始为 1, 指向根节点.
• 检测该节点有没有孩子节点, 如果没有孩子节点, 则完成 ShiftDown 操作
• 检测孩子时, 因为是完全二叉树, 所以只需要先看是否有左孩子 (2 * k).
• 和孩子中较大元素进行比较, 如果小于较大孩子, 则与之交换, 否则完成 ShiftDown 操作.

具体代码实现如下:

Item extractMax() {
    Item ret = data[1];
    data[1] = data[count -1];
    shiftDown(1);
    return Item;
}

void shiftDown(int k) {
    while (2 * k <= count) {
        int j = 2 * k;
        if (j + 1 <= count && data[j + 1] > data[j]) {
            j++;
        }
        if (data[j] <= data[k]) {
            break;
        }
        swap(data[k], data[j]);
        k = j;
    }
    
}

堆排序

有了堆这一数据结构, 我们可以轻易实现一个堆排序算法. 最简单的实现就是将数据依次放入一个堆中, 再依次取出, 就得到了一个有序数据.

template<typename T>
void heapSort1(T arr[], int n) {
    MaxHeap<T> maxHeap = MaxHeap<T>(n);
    for (int i = 0; i < n; i++) {
        maxHeap.insert(arr[i]);
    }

    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}

Heapify

上面我们额外开辟了一个空间来进行堆排序. 下面我们介绍一个操作, 将一个不满足堆的数组变成堆.

这个过程实现也很简单, 使用从小到大的思路即可.

一个单一的元素肯定满足堆的性质, 我们首先将所有叶子节点看做一个堆, 然后依次, 从后向前, 一个一个的将元素加入到子堆中, 加入后, 执行 shiftDown 操作, 就可以使得新生成的子堆也满足堆的性质. 直到最后一个根节点也加入进来, 则数组满足堆的性质. 具体实现起来也非常简单.

MaxHeap(Item arr[], int n) {
    data = new Item[n + 1];
    capacity = n;
    for (int i = 0; i < n; i++) {
        data[i + 1] = arr[i];
    }
    for (int i = count / 2; i >= 1; i--) {
        shiftDown(i);
    }
}

使用 Heapify 的操作, 完成的堆排序算法

template<typename T>
void heapSort2(T arr[], int n) {
    MaxHeap<T> maxHeap = MaxHeap<T>(arr, nullptr);
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}

原地堆排序

• 一个堆
• 将最大元素与末尾元素交换
• shiftdown 操作

template<typename T>
void __shiftDown(T arr[], int n, int k) {
    while (2 * k + 1 < n) {
        int j = 2 * k + 1;
        if (j + 1 < n && arr[j] < arr[j + 1]) {
            j += 1;
        }
        if (arr[k] >= arr[j]) {
            break;
        }
        swap(arr[k], arr[j]);
        k = j;
    }
}

template<typename T>
void heapSort(T arr[], int n) {
    for (int i = (n - 1) / 2; i >= 0; i--) {
        __shiftDown(arr, n, i);
    }

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        __shiftDown(arr, i, 0);
    }
}