lickylin 2020-02-22
for(int i = 1; i <= N; i++){ father[i] = i; }
int findFather(int x){ while(x != father){ x = father[x]; } return x; } int findFather(int x){ if(x == father[x]) return x; else return findFather(father[x]); }
void Union(int a, int b){ int faA = findFather(a); int faB = findFather(b); if(faA != faB){ father[faA] = faB; } }
int findFather(int x){ //由于x在下面的while中会变成根结点,因此先把原先的x保存一下 int a = x; while(x != father[x]){ x = father[x]; } //到这里,x存放的是根结点,下面把路径上所有的结点的father都改成根结点 while(a != father[a]){ int z = a; a = father[a];//a回溯父亲结点 father[z] = a;//把原来的结点a的父亲改为根结点 } return x;//返回根结点 }
//对于heap数组在[low, high]的范围进行向下调整 //其中low为欲调整结点的数组下标,high一般为堆的最后一个元素的数组下标 void downAdjust(int low, int high){ int i = low, 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[j], heap[i]); i = j; j = i * 2; }else{ break; } } }
void createHeap(){ for(int i = n / 2; i >= 1; i--){ downAdjust(i, n); } }
void deleteTop(){ heap[1] = heap[n--]; downAdjust(1, n); }
//对于heap数组在[low, high]的范围进行向上调整 //其中low为欲调整结点的数组下标设置为1,high一般为堆的最后一个元素的数组下标 void upAdjust(int low, int high){ int i = high, j = i / 2;//i为欲调整结点,j为其父亲 while(j >= low){ if(heap[j] < heap[i]){ swap(heap[j], heap[i]); i = j; j = i / 2; }else{ break; } } } //添加元素 void insert(int x){ heap[++n] = x;//让元素个数加1,然后将数组末尾赋值为x upAdjust(1, n);//向上调整新加入的结点n }
void heapSort(){ createHeap(); for(int i = n; i > 1; i--){ swap(heap[i], heap[1]); downAdjust(1, i - 1); } }