秋招各大廠，必考的優先佇列和堆排序
摘要：
秋招過了，春招還會遠麼？真實面試題：工作一年同事跳槽，去某為，就考了一道：用陣列實現堆排序，下面就來介紹一下堆排序的實現
堆和優先佇列
堆的定義
n個元素的序列k={k0,k1,……,kn-1},當且僅滿足條件
(1)ki >= k2i+1 和 ki >= k2i+...
秋招過了，春招還會遠麼？真實面試題：工作一年同事跳槽，去某為，就考了一道：用陣列實現堆排序，下面就來介紹一下堆排序的實現
堆和優先佇列
堆的定義
n個元素的序列k={k0,k1,……,kn-1},當且僅滿足條件
(1)ki >= k2i+1 和 ki >= k2i+2 (2)ki <= k2i+1 和 ki <= k2i+2
(1)稱為大根堆 (2)稱為小根堆
可以把堆看成完全二叉樹。
優先佇列
優先佇列是一種常見的抽象資料型別，它與"佇列"不同，不遵循"先進先出"原則，而遵循"最大元素先出"原則， 出隊和優先順序有關 。
優先佇列的基本操作有三個：
(1) 向優先佇列裡插入一個元素
(2) 在優先佇列找出最大元素
(3) 刪除優先佇列中最大元素
可以用堆來實現優先佇列
二叉堆
最大堆定義
堆中任一節點總是大於其父節點的值，堆總是一顆完全二叉樹，本篇部落格以實現最大堆為主
陣列實現二叉堆
用二叉樹來實現堆，是比較好的，也可以用二叉樹的左右指標來實現，但這種太麻煩；因為是完全二叉樹，所以也可以用陣列來實現二叉堆，見下圖：PS：依舊是全部落格園最醜圖
說明：將陣列的值來抽象成二叉樹，二叉樹圖上的紅色字就表示陣列的下標，而且還能總結出藍色字型的規律。
構建一個堆類，程式碼如下：
template<typename Item>
class MaxHeap{
private:
Item *data;//陣列
int count;//堆的大小
int capacity;//堆的容量
public:
//建構函式 構建一個空堆
MaxHeap(int capacity){
data = new Item[capacity+1];
count = 0;
this->capacity = capacity;
}
}；
最大堆的實現
最大堆上插入元素 shift up
直接上圖，再說明，如下圖：
程式碼如下：
void shiftUp(int k){
while(k>1 && data[k/2]<data[k]){
swap(data[k/2],data[k]);
k /= 2;
}
}
//向最大堆中插入元素
void insert(Item item){
assert(count+1<=capacity);
data[count+1] = item;
shiftUp(count+1);
count++;
}
最大堆上取出元素 shift down
直接上圖，如下：
程式碼如下：
void shiftDown(int k){
while(2*k<=count){
int j = 2*k;
if(j+1<count && data[j+1]>data[j]) j++; //右孩子比左孩子，j移動
if(data[k]>data[j]) break;
swap(data[k],data[j]);
k=j;
}
}
//從最大堆中取出堆頂元素
Item extracMax(){
assert(count > 0);
Item ret = data[1];
swap(data[1],data[count]);
count--;
shiftDown(1);
return ret;
}
實現堆排序
有了插入和取出，就可以實現堆排序了，程式碼如下：
//將所有元素插入堆，再取出
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.extracMax();
}
執行結果如下：
heapify實現最大堆
建構函式實現heapify過程
就是用建構函式來實現最大堆，見下圖：
程式碼如下：
//建構函式，通過給定陣列實現最大堆 O(n)
MaxHeap(Item arr[],int n){
data = new Item[n+1];
capacity = n;
for(int i=0;i<n;i++)
data[i+1] = arr[i];
count = n;
for(int i=count/2;i>=1;i--)
shiftDown(i);
}
// heapSort2, 藉助我們的heapify過程建立堆
// 此時, 建立堆的過程時間複雜度為O(n), 將所有元素依次從堆中取出來, 實踐複雜度為O(nlogn)
// 堆排序的總體時間複雜度依然是O(nlogn), 但是比上述heapSort1效能更優, 因為建立堆的效能更優
template<typename T>
void heapSort2(T arr[], int n){
MaxHeap<T> maxheap = MaxHeap<T>(arr,n);
for( int i = n-1 ; i >= 0 ; i-- )
arr[i] = maxheap.extracMax();
}
總體程式碼
Heap.h標頭檔案，程式碼如下：
#ifndef HEAP_H_
#define HEAP_H_
#include<algorithm>
#include<cassert>
using namespace std;
template<typename Item>
class MaxHeap{
private:
Item *data;//陣列
int count;//堆的大小
int capacity;//堆的容量
void shiftUp(int k){
while(k>1 && data[k/2]<data[k]){
swap(data[k/2],data[k]);
k /= 2;
}
}
void shiftDown(int k){
while(2*k<=count){
int j = 2*k;
if(j+1<count && data[j+1]>data[j]) j++; //右孩子比左孩子，j移動
if(data[k]>data[j]) break;
swap(data[k],data[j]);
k=j;
}
}
public:
//建構函式 構建一個空堆
MaxHeap(int capacity){
data = new Item[capacity+1];
count = 0;
this->capacity = capacity;
}
//建構函式，通過給定陣列實現最大堆 O(n)
MaxHeap(Item arr[],int n){
data = new Item[n+1];
capacity = n;
for(int i=0;i<n;i++)
data[i+1] = arr[i];
count = n;
for(int i=count/2;i>=1;i--)
shiftDown(i);
}
~MaxHeap(){
delete[] data;
}
//返回堆中的元素個數
int size(){
return count;
}
//判斷是否為空
bool isEmpty(){
return count==0;
}
//向最大堆中插入元素
void insert(Item item){
assert(count+1<=capacity);
data[count+1] = item;
shiftUp(count+1);
count++;
}
//從最大堆中取出堆頂元素
Item extracMax(){
assert(count > 0);
Item ret = data[1];
swap(data[1],data[count]);
count--;
shiftDown(1);
return ret;
}
};
#endif
View Code
heap.cpp如下：
#include<iostream>
#include<algorithm>
#include"Heap.h"
#include "SortTestHelper.h"
//將所有元素插入堆，再取出
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.extracMax();
}
// heapSort2, 藉助我們的heapify過程建立堆
// 此時, 建立堆的過程時間複雜度為O(n), 將所有元素依次從堆中取出來, 實踐複雜度為O(nlogn)
// 堆排序的總體時間複雜度依然是O(nlogn), 但是比上述heapSort1效能更優, 因為建立堆的效能更優
template<typename T>
void heapSort2(T arr[], int n){
MaxHeap<T> maxheap = MaxHeap<T>(arr,n);
for( int i = n-1 ; i >= 0 ; i-- )
arr[i] = maxheap.extracMax();
}
int main(){
int n = 10;
// 測試1 一般性測試
//cout<<"Test for random array, size = "<<n<<", random range [0, "<<n<<"]"<<endl;
int* arr1 = SortTestHelper::generateRandomArray(n,0,n);
int* arr2 = SortTestHelper::copyIntArray(arr1, n);
SortTestHelper::testSort("Heap Sort 1", heapSort1, arr1, n);
SortTestHelper::testSort("Heap Sort 2", heapSort2, arr2, n);
for(int i=0;i<n;i++)
cout << arr1[i] << " ";
cout << endl;
for(int i=0;i<n;i++)
cout << arr2[i] << " ";
cout << endl;
delete[] arr1;
delete[] arr2;
cout <<endl;
}
View Code
十一月總結
正如前面所說：秋招已過，春招還會遠麼？18年還有一個月就要結束了，感覺比大學時過的時間還快！有個戰略要改變，之前定的年底之前一直要學資料結構和演算法，這個計劃要伴隨整個職業生涯了，最起碼一直到明年5月，都要一直堅持學！
11月主要完成的
- 學了python
- 資料結構和演算法完成了整體架構的學習和整理
- 複習C++和作業系統
12月計劃
- 最主要的計劃就是有效深入的學習資料結構和演算法
- 鞏固C++、作業系統和網路程式設計