数据结构-堆排序

文章目录

• ​​1、向下调整​​
• ​​2、向上调整​​
• ​​3、建立堆​​
• ​​4、堆排序​​
• ​​5、删除堆首​​
• ​​6、增加元素​​
• ​​7、完成代码​​

堆是由一维数组存储的完全二叉树，下标从1开始，因此下标最大的非叶子节点为n/2（可以动手画画想想）。本篇文章以建立大根堆为例。

1、向下调整

使用向下调整方式建立堆时，直接选择非叶子节点。

void down(int low, int high){
 
  int i = low;
  int j = i*2;
  
  while(j<= high){
    //如果含有右孩子，并且右孩子大于左孩子则将j置为右孩子
    if(j+1 <= high && heap[j+1] > heap[j])j = j+1;
     
    //如果孩子中的最大值大于自身，交换
    if(heap[j] > heap[i]){
      swap(heap[i],heap[j]);
      //继续向下调整
      i = j;
      j=i*2;
    }else{
      break;
    }
  }
}

2、向上调整

向上调整思路简单，有没有父亲节点，自身是否大于父亲节点。

void up(int low,int high){
 
  int i = high;
  int j = i/2;
  
  while(j >= low){
    if(heap[i] > heap[j]){
      swap(heap[j],heap[i]);
      i = j;
      j = i/2;
    }else{
      break;
    }
  }
  
}

3、建立堆

void creatheap(){
  for(int i = n/2; i >= 1;i--){
    
    down(i,n);
  }
}

4、堆排序

堆排序非常简单，明白了如何建成大根堆，每次把顶点（最大值）放到最尾端就不要再动了，最尾端向前移动一个位置，然后再建立大根堆，再将最大值放到最尾端。直接看代码更清晰。

void heapsort(){
  for(int i = n; i > 1; i--){
    swap(heap[1],heap[i]);
    down(1,i-1);
  }
}
//是不是soeasy

5、删除堆首

void deleteTop(){
  heap[1] = heap[n--];
  down(1,n);
}

6、增加元素

void insert(int x){
  heap[++n]=x;
  //插入元素堆要重新调整 
  creatheap();
}

总之，无论使用什么的操作吧，插入，删除都好，你心里面要清楚，你的操作是否导致你的堆还是大根堆或者时小根堆，明白这一点再进行下一步的操作。

7、完成代码

输入

5
2 8 5 1 3

输出

1 2 3 5 8

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
const int MAXN = 1005;
int heap[MAXN];
int n;
void up(int low,int high){
 
  int i = high;
  int j = i/2;
  
  while(j >= low){
    if(heap[i] > heap[j]){
 
      swap(heap[j],heap[i]);
      i = j;
      j = i/2;
    }else{
      break;
    }
  }
  
}
void down(int low, int high){
 
  int i = low;
  int j = i*2;
  
  while(j<= high){
    if(j+1 <= high && heap[j+1] > heap[j])j = j+1;
    if(heap[j] > heap[i]){
      swap(heap[i],heap[j]);
      i = j;
      j=i*2;
    }else{
      break;
    }
  }
}


void creatheap(){
  for(int i = n/2; i >= 1;i--){
    down(i,n);
  }
}

void heapsort(){
  for(int i = n; i > 1; i--){
    swap(heap[1],heap[i]);
    down(1,i-1);
  }
}

void deleteTop(){
  heap[1] = heap[n--];
  down(1,n);
}

void insert(int x){
  heap[++n]=x;
  //插入元素堆要重新调整 
  creatheap();
}

void print(){
  for(int i = 1; i <=n; i++){
    cout << heap[i] << " ";
  }
}
int main(){
   
   cin >> n;
   
   for(int i = 1; i <= n; i++){
    cin >> heap[i];
   }
   
  //堆中从n/2个节点开始为非叶子节点 
  creatheap();
  heapsort(); 
  insert(4);
  heapsort();
  print();
  return 0;
}