public void offer(int val) {//插入操作
if(isFull()) {
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize] = val;
usedSize++;//11
siftUp(usedSize-1);
}
public void siftUp(int child) {
int parent = (child-1)/2;
while (parent >= 0) {
if(elem[child] > elem[parent]) {
swap(child,parent);
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
public int poll() {//删除操作,将首元素和尾元素互换后维修大根堆
if(isEmpty()) {
return -1;
}
int old = elem[0];
swap(0,usedSize-1);
usedSize--;
siftDown(0,usedSize);
return old;
}
public void siftDown(int parent,int end) {
int child = 2*parent+1;
while (child < end) {
if(child+1 < end && elem[child] < elem[child+1]) {
child++;
}
//child下标 就是 左右孩子的最大值
if(elem[child] > elem[parent]) {
swap(child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
在堆(无论是大根堆还是小根堆)的插入和删除操作中,需要两个不同的方法来维护堆的性质。这是因为插入和删除操作对堆的影响不同,因此维护堆性质的方式也不同。
插入操作(siftUp):
- 当新的元素被添加到堆的末尾时,它可能破坏堆的性质。因为新元素是最后被添加的,它总是处于叶子节点的位置。
- 要修复这个问题,我们需要将新元素与其父节点进行比较,并根据需要交换它们的位置。这个过程会一直向上进行,直到新元素到达正确的位置,或者它不再比其父节点大(对于大根堆)。
- 因此,
siftUp
方法是从下往上调整堆的,它确保新插入的元素在堆中正确地“上浮”到合适的位置。删除操作(通常是删除堆顶元素,然后siftDown):
- 当堆顶元素(对于大根堆来说,是最大值)被删除时,我们需要用堆的最后一个元素来替换堆顶的位置,并重新调整堆以保持其性质。
- 由于新放在堆顶的元素可能小于其子节点,我们需要将它“下沉”到正确的位置。这通常是通过与较大的子节点进行比较和交换来实现的。
siftDown
方法是从上往下调整堆的,它确保新放在堆顶的元素在堆中正确地“下沉”到合适的位置。
简而言之,siftUp
和 siftDown
方法的目的是在插入和删除操作后重新调整堆,以确保它仍然满足堆的性质(即父节点的值总是大于或等于其子节点的值,对于大根堆来说)。这两个方法分别处理从底部添加新元素和从顶部删除元素的情况,因此它们的实现方式有所不同。