算法学习之--堆排序

港控/mmm° 2022-08-24 15:30 116阅读 0赞

堆排序主要是堆性质的维护

1.push可看成update（假设最尾部有一个key异常小的元素，该元素更新为需要push的值）；

2.update复杂度可用空间换时间成O(lgN)（添加一个arrayIndex数组，记录维护堆形式的位置变换关系）；

3.update由于只变大，因此只需与父节点比较即可；

4.pop出的肯定是第一个，然后将最末尾的放到第一个位置，重新建堆即可；

5./使用堆排序之前需要将输入建立成最大堆；

6.堆形式维护，父子间找最大的，交换位置，默认子树已满足堆形式；

7.建堆时只需要从中间往前建即可。

//---------------------------------------------华丽的分割线----------------------------------------------------------------------------------------------------------------------------------------------------------------------

// BinaryHeap.cpp : Defines the entry point for the console application.

//  
  
  
\#include "stdafx.h"  
\#include <stdio.h>  
\#include <vector>  
  
  
  
  
class BinaryHeap  
\{  
public:  
BinaryHeap()  
\{  
m\_HeapSize = 1;  
m\_Container.push\_back(0xffffffff);  
\}  
  
  
BinaryHeap(int\* a, int len)  
\{  
m\_HeapSize = 1 + len;  
m\_Container.push\_back(0xffffffff);  
m\_Container.insert(m\_Container.end(), a, a+len);  
for (int idx=len/2; idx>=1; --idx)  
\{  
heapify(idx);  
\}  
\}  
  
  
// pop出的肯定是第一个，然后将最末尾的放到第一个位置，重新建堆即可  
int Pop()  
\{  
int max = m\_Container\[1\];  
m\_Container\[1\] = m\_Container\[m\_HeapSize-1\];  
m\_HeapSize--;  
heapify(1);  
return max;  
\}  
  
  
void Push(int value)  
\{  
m\_Container.push\_back(value);  
m\_HeapSize++;  
increse(m\_HeapSize-1);  
\}  
  
  
void Update(int idx, int value)  
\{  
int realIdx = 1;  
for ( realIdx=1; realIdx<m\_HeapSize; ++realIdx)  
\{  
if (m\_Container\[realIdx\] == idx)  
\{  
break;  
\}  
\}  
m\_Container\[realIdx\] = value;  
increse(realIdx);  
\}  
  
  
// 使用堆排序之前需要将输入建立成最大堆  
void Sort()  
\{  
while (1)  
\{  
printf("%d,", Pop());  
if (m\_HeapSize-1==0)  
\{  
break;  
\}  
\}  
\}  
  
  
void Print()  
\{  
printf("heap size:%d;\\t", m\_HeapSize-1);  
for (int i=1; i<m\_HeapSize; ++i)  
\{  
printf("%d,", m\_Container\[i\]);  
\}  
printf("\\r\\n");  
\}  
  
  
protected:  
// 建堆  
// 父子间找最大的，交换位置  
// 默认子树已满足堆形式  
void heapify(int idx)  
\{  
int left = idx<<1;  
int right = left + 1;  
  
int max = idx;  
while (1)  
\{  
if (left<m\_HeapSize && m\_Container\[left\]>m\_Container\[idx\])  
\{  
max = left;  
\}  
if (right<m\_HeapSize && m\_Container\[right\]>m\_Container\[max\])  
\{  
max = right;  
\}  
  
  
if (max==idx)  
\{  
break;  
\}  
  
  
int temp = m\_Container\[idx\];  
m\_Container\[idx\] = m\_Container\[max\];  
m\_Container\[max\] = temp;  
  
  
idx = max;  
left = idx<<1;  
right = left + 1;  
\}  
\}  
  
  
// idx处key值增加后重新建堆  
// 只需和父节点比较即可  
void increse(int idx)  
\{  
int parent = idx>>1;  
while (idx>1 && m\_Container\[parent\]<m\_Container\[idx\])  
\{  
int temp = m\_Container\[parent\];  
m\_Container\[parent\] = m\_Container\[idx\];  
m\_Container\[idx\] = temp;  
idx = parent;  
parent = idx>>1;  
\}  
\}  
  
  
private:  
std::vector<int> m\_Container;  
int m\_HeapSize;  
\};  
  
  
  
  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
int test\[\] = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\};  
BinaryHeap heap(test, sizeof(test)/sizeof(int));  
heap.Print();  
/\*BinaryHeap heap;  
for (int i=0; i<sizeof(test)/sizeof(int); ++i)  
\{  
heap.Push(test\[i\]);  
heap.Print();  
\}\*/  
  
  
heap.Sort();  
  
  
//heap.Update(7, 17);  
//heap.Print();  
  
  
for (int i=0; i<sizeof(test)/sizeof(int); ++i)  
\{  
heap.Pop();  
heap.Print();  
\}  
  
  
return 0;  
\}