前言
堆一般是由數(shù)組實(shí)現(xiàn)的完全二叉樹(shù),堆的排序也屬于選擇排序,JAVA jdk中的PriorityQueue就是采用的小根堆實(shí)現(xiàn)的升序排序,因此要了解PriorityQueue就必須掌握堆的排序币他，這里就采用大根堆方式來(lái)實(shí)現(xiàn)默認(rèn)降序方式的PriorityQueue
一：堆排序
堆排序步驟：
1： 將無(wú)序數(shù)組構(gòu)造成一個(gè)大根堆(或小根堆), 大(小)根堆的構(gòu)造就是將最后一個(gè)非葉子結(jié)點(diǎn)到根節(jié)點(diǎn)進(jìn)行大小調(diào)整(結(jié)點(diǎn)的調(diào)整從上至下)以滿足大(小)根堆的概念
直接上圖(圖中采用的是大根堆方式),排序無(wú)序數(shù)組 12 2 6 30 17 5 22 18
大根堆調(diào)整.png
從圖中可以看出最后一個(gè)非葉子結(jié)點(diǎn)是30, 就需要依次調(diào)整 30 6 2 12結(jié)點(diǎn)
2：將堆根(數(shù)組首元素)與末尾元素交換, 即相當(dāng)于使數(shù)組末尾元素為最大, 再將除已經(jīng)排列出的最大的尾元素前的數(shù)組繼續(xù)大(小)根堆調(diào)整, 由于第一步已經(jīng)排列出大(小)根堆, 此時(shí)只需要直接從根節(jié)點(diǎn)開(kāi)始向下調(diào)整即可
替換并調(diào)整.png
3：代碼實(shí)現(xiàn)(大根堆實(shí)現(xiàn)升序)
class HeapSort {
public:
/**
* 堆排序
* @param arrs
* @param len
*/
static void sort(int *arrs, int len) {
for (int i = (len >> 1) - 1; i >= 0; --i) {
siftDown(arrs, len, i);
}
for (int i = len - 1; i > 0 ; --i) {
swap(arrs, 0, i);
siftDown(arrs, i, 0);
}
}
/**
* 從上至下調(diào)整大根堆
* @param arrs
* @param len
* @param index
*/
static void siftDown(int *arrs, int len, int index) {
while (index < len >> 1) {
int maxChildIndex = (index << 1) + 1; //左右孩子中找出最大值的孩子的位置
int rightChildIndex = maxChildIndex + 1;
if (rightChildIndex < len && arrs[rightChildIndex] > arrs[maxChildIndex]) {
maxChildIndex = rightChildIndex;
}
if (arrs[maxChildIndex] <= arrs[index]) return;
swap(arrs, index, maxChildIndex);
index = maxChildIndex;
}
}
/**
* 交換
* @param arrs
* @param l
* @param r
*/
static void swap(int *arrs, int l, int r) {
int tmp = arrs[l];
arrs[l] = arrs[r];
arrs[r] = tmp;
}
};
二：PriorityQueue降序?qū)崿F(xiàn)
PriorityQueue原理與堆排序類似,由于每次在隊(duì)列中加入元素的時(shí)候前面的元素已經(jīng)做好了大根堆調(diào)整,所以每次在隊(duì)列中加入元素的時(shí)候,從下至上與父結(jié)點(diǎn)比較,小于父節(jié)點(diǎn)不做處理, 大于父節(jié)點(diǎn)時(shí)與父節(jié)點(diǎn)替換,再與父點(diǎn)節(jié)比較,刪除節(jié)點(diǎn)時(shí)與堆排序的第2步一致
直接上代碼
template <class E>
struct Greater {
constexpr bool operator() (const E &left, const E &right) const {
return left > right;
}
};
template <class E>
struct LessEqual {
constexpr bool operator() (const E &left, const E &right) const {
return left <= right;
}
};
template <class E, class C = Greater<E> >
class PriorityQueue {
private:
E *queue;
//類似JDK中的Comparable
C comparator;
int len = 0;
//初始數(shù)組大小
int capacity = 11;
/**
* 擴(kuò)充數(shù)組
* @param minCapacity
*/
void grow();
/**
* 從下往上調(diào)整根堆
* @param index
* @param v
*/
void siftUp(int index, const E &e);
/**
* 從上往下調(diào)整根堆
* @param index
* @param v
*/
void siftDown(int index, const E &e);
public:
PriorityQueue();
PriorityQueue(int capacity);
~PriorityQueue();
//隊(duì)列是否空
bool isEmpty();
/**
* 優(yōu)先隊(duì)列中添加元素
* @param e
*/
void push(const E &e);
/**
* 彈出隊(duì)首元素
* @return
*/
E poll();
//不彈出,查看首元素
E peek();
};
//默認(rèn)大小11
template <class E, class C>
PriorityQueue<E, C>::PriorityQueue() : PriorityQueue(11) {
}
template <class E, class C>
PriorityQueue<E, C>::PriorityQueue(int capacity) {
assert(capacity > 1);
this->capacity = capacity;
this->queue = (E*) malloc(sizeof(E) * capacity);
}
template <class E, class C>
PriorityQueue<E, C>::~PriorityQueue() {
if (this->queue) {
free(this->queue);
this->queue = NULL;
}
}
/**
* 這里忽略擴(kuò)充數(shù)組后大小超過(guò)int最大值
* @tparam E
* @tparam C
* @param minCapacity
*/
template <class E, class C>
void PriorityQueue<E, C>::grow() {
//擴(kuò)充前的數(shù)組長(zhǎng)度超過(guò)64時(shí)擴(kuò)充1.5倍
capacity = capacity + ((capacity < 64) ? (capacity + 2) : (capacity >> 1));
queue = (E*) realloc(queue, sizeof(E) * capacity);
}
template <class E, class C>
void PriorityQueue<E, C>::siftUp(int index, const E &e) {
int parentIndex;
while (index > 0) {
parentIndex = (index - 1) >> 1;//找出父節(jié)點(diǎn)的位置
if (comparator(queue[parentIndex], e)) {//父節(jié)點(diǎn)大于該節(jié)點(diǎn),跳出循環(huán)
break;
}
queue[index] = queue[parentIndex];
index = parentIndex;
}
queue[index] = e;
}
template <class E, class C>
void PriorityQueue<E, C>::siftDown(int index, const E &e) {
while (index < len >> 1) {
int maxChildIndex = (index << 1) + 1;//左孩子與右孩子比較得出最大孩子的位置
int rightChildIndex = maxChildIndex + 1;
if (rightChildIndex < len && comparator(queue[rightChildIndex], queue[maxChildIndex])) {
maxChildIndex = rightChildIndex;
}
if (!comparator(queue[maxChildIndex], e)) {
break;
}
queue[index] = queue[maxChildIndex];
index = maxChildIndex;
}
queue[index] = e;
}
template <class E, class C>
bool PriorityQueue<E, C>::isEmpty() {
return len <= 0;
}
template <class E, class C>
void PriorityQueue<E, C>::push(const E &e) {
if (this->len >= capacity) {
grow();
}
siftUp(this->len, e);
this->len++;
}
template <class E, class C>
E PriorityQueue<E, C>::poll() {
assert(len > 0);
E max = queue[0];
this->len--;
if (this->len > 0) {
siftDown(0, queue[len]);
}
return max;
}
template <class E, class C>
E PriorityQueue<E, C>::peek() {
assert(len > 0);
return queue[0];
}
