Algorithm Part I:Priority Queues

时间:2022-09-07 20:59:50

1.binary heap实现

BinaryHeap.h

#ifndef BINARYHEAP_H
#define BINARYHEAP_H class BinaryHeap
{
public:
BinaryHeap(int N);
bool isEmpty();
void exchange(int i,int j);
void insert(int key);
int delMax();
int getMax();
virtual ~BinaryHeap();
protected:
private:
int N;
int * data;
void swim(int key);
void sink(int key);
}; #endif // BINARYHEAP_H

BinaryHeap.cpp

#include "BinaryHeap.h"
#include <stdlib.h> BinaryHeap::BinaryHeap(int N)
{
this->N = 0;
this->data = (int *)malloc(sizeof(int)*(N+1));
} BinaryHeap::~BinaryHeap()
{
} bool BinaryHeap::isEmpty()
{
return N == 0;
} void BinaryHeap::exchange(int i,int j)
{
int temp = this->data[i];
this->data[i] = this->data[j];
this->data[j] = temp;
} void BinaryHeap::swim(int key)
{
while(key > 1 && data[key/2] < data[key])
{
exchange(key/2,key);
key = key/2;
}
} void BinaryHeap::insert(int key)
{
N++;
data[N] = key;
swim(N);
} void BinaryHeap::sink(int key)
{
while(key*2 <= N)
{
int j = key*2;
if(j < N && data[j] < data[j+1])
j++;
if(data[key] >= data[j])
break;
else
{
exchange(key,j);
key = j;
}
}
} int BinaryHeap::delMax()
{
int max = data[1];
exchange(1,N-1);
N--;
sink(1);
return max;
} int BinaryHeap::getMax()
{
return data[1];
}

main.c

#include <iostream>
#include "BinaryHeap.h" using namespace std; int main()
{
BinaryHeap * bp = new BinaryHeap(10);
bp->insert(3);
bp->insert(2);
bp->insert(1);
bp->insert(5);
bp->insert(8);
bp->insert(7);
cout << bp->getMax() << "\n";
bp->delMax();
cout << bp->getMax() << "\n";
char c;
cin >> c;
return 0;
}

各操作时间复杂度的分析:

Algorithm Part I:Priority Queues

2.堆排序

堆排序的主要步骤:

Algorithm Part I:Priority Queues

(1)建堆

Algorithm Part I:Priority Queues

(2)依次移除最大元素,将它放到数组的尾端。

Algorithm Part I:Priority Queues

3.各种排序算法的分析

Algorithm Part I:Priority Queues

版权声明:本文博客原创文章,博客,未经同意,不得转载。