• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

堆结构是由数组实现的完全二叉树结构。

在一棵完整的二叉树中,如果每个子树的最大值都在顶部,那么它就是大根堆.

在一棵完整的二叉树中,如果每个子树的最小值都在顶部,那么它就是小根堆.

堆结构有两个操作:heapInsert和heapify。

优先级队列结构是堆结构。

大小

I左节点:2 * i 1

右节点:2 * i 2

父节点:(i-1)/2

保持健康

插入元素时,初始位置是当前heaspsize的位置,然后与自己的父节点进行比较。如果比自己的父节点大,就一直交换到根节点。如果没有,停止。这个操作是heapInsert。

public static void heap insert(int[]arr,int index) {

//当当前值小于其父节点时停止

//当索引为0时。指数-1/2也是0。它也停止了。

while(arr[index]arr[(index-1)/2]){

swap(arr,index,((index-1)/2));

//交换后,更新索引

index=(index-1)/2;

}

}

当去掉0位置的数字(获得最大值)时,调整堆的结构保持为大根堆。

最后一个数字与0交换,然后调整。调整后,最后一个号码不在堆里。破碎的

你的左孩子和右孩子PK,选最大的。并且再次pk自己。

停的条件:左右孩子没有自己大,没有左右孩子。

public static void heapify(int[]arr,int index,int size) {

int left=2 * index 1;//左子下标

While (left size) {//有左孩子,

//获取左侧子节点和右侧子节点的大值索引

int largest=left 1 size arr[left 1]arr

?左1 :左;

//孩子比自己最大。

largest=arr[largest] arr[index]?最大:指数;

if (largest==index) {

//如果你年龄最大,那就退出。

打破;

}

//孩子比自己大,交换

swap(arr,maximum,index);

//更新索引并继续向下

指数=最大;

//更新左边的子下标

左=2 *索引1;

}

}

分类

public void userSort(int[] arr) {

if (arr==null || arr.length 2) {

返回;

}

int heapSize=arr.length

//插入堆,只是个大根堆,还没排序

for(int I=0;长度;i ) {

heapInsert(arr,I);

}

//开始调整。当前最大值为0,依次与最后一个位置交换,所以依次排列。

swap(arr,0,-heap size);

while (heapSize 0) {

heapify(arr,0,heap size);

swap(arr,0,-heap size);

}

}

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now