heap

建堆 插入元素 删除元素 堆排序 判断堆 寻找第一个不符合堆的位置 ——algorithm

建堆 make_heap

默认建大根堆,O(n)

1
2
3
4
5
6
7
8
9
10
11
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

return 0;
}


插入元素 push_heap

将最后一个元素插入原来的堆中(要保证在调用push_heap前,除开最后一个数已经是一个堆),O(nlgn)
并且制定堆的类型要与之前构建的相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

v1.push_back(20);
push_heap(v1.begin(),v1.end()); //同样 默认大根堆
v2.push_bavk(20);
push_heap(v2.begin(),v2.end(),cmp); //小根堆

return 0;
}

删除元素 pop_heap

交换首尾元素,然后将除了最后一个元素的部分重新调整成堆。
要保证在调用pop_heap前已经是一个堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

pop_heap(v1.begin(),v1.end()); //同样 默认大根堆
v1.pop_back(); //删除最后一个元素
pop_heap(v2.begin(),v2.end(),cmp); //小根堆
v2.pop_back();

return 0;
}


堆排序 sort_heap

在原来已经是堆的情况下调用进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

sort_heap(v1.begin(),v1.end()); //同样 默认大根堆
sort_heap(v2.begin(),v2.end(),cmp); //小根堆

return 0;
}


C++11新成员

判断是否为堆 is_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

bool judge1=is_heap(v1.begin(),v1.end()); //同样 默认大根堆
bool judge2=is_heap(v2.begin(),v2.end(),cmp); //小根堆

return 0;
}

找到第一个不构成堆的元素 is_heap_until

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool cmp(int a,int b){
return a>b; //注意是大于
}
int main(){
vector<int> v1(6,5,3,4,2,1);
vector<int> v2(6,5,3,4,2,1);
make_heap(v1.begin(),v1.end()); //默认构建大根堆
make_heap(v2.begin(),v2.end(),cmp); //小根堆

vector<int>:: iteraotr it=is_heap_until(v1.begin(),v1.end()); //同样 默认大根堆
vecotr<int>:: iterator it2=is_heap_until(v2.begin(),v2.end(),cmp); //小根堆

return 0;
}
Donate comment here