堆的操作

痛定思痛。 2021-09-23 22:32 393阅读 0赞

# 向堆中添加元素 #

**上浮操作**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

**代码：**

public void swap(int i, int j) { 
    
            if (i < 0 || i >= size || j < 0 || j >= size)
                throw new IllegalArgumentException("Index is illegal.");
    
            E t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    
        // 向堆中添加元素
        public void add(E e){ 
            data.addLast(e);
            siftUp(data.getSize() - 1);
        }
    
        private void siftUp(int k){ 
    
            while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){ 
                data.swap(k, parent(k));
                k = parent(k);
            }
        }

# 向堆中取出元素 #

**下沉操作**

**只能取出最大的元素。小技巧：我们堆中的最后的一个元素顶到堆顶去，再把最后一个元素删除掉。从元素的个数上，我们成功地减少了一个元素，并且我们真正减少的元素就是原来堆顶的元素，此时仍然满足完全二叉树的性质的。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

**现在问题在于堆顶的元素打破了堆的性质。 即每个节点必须大于等于孩子节点。此时我们要进行一些调整。每次我们要下沉的元素都要和它的两个孩子节点比较，如果两个孩子节点中最大的元素比他自己还要大的话，那么就将他两调换位置。一直下沉到满足堆的性质为止**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]  
**代码：**

//交换两个函数位置
        public void swap(int i, int j){ 
    
            if(i < 0 || i >= size || j < 0 || j >= size)
                throw new IllegalArgumentException("Index is illegal.");
    
            E t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    
       // 看堆中的最大元素
        public E findMax() { 
            if (data.getSize() == 0)
                throw new IllegalArgumentException("Can not findMax when heap is empty.");
            return data.get(0);
        }
    
        // 取出堆中最大元素
        public E extractMax() { 
    
            E ret = findMax();
    
            data.swap(0, data.getSize() - 1);
            data.removeLast();
            siftDown(0);
    
            return ret;
        }
    
        private void siftDown(int k) { 
    
            while (leftChild(k) < data.getSize()) { 
                int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
                if (j + 1 < data.getSize() &&
                        data.get(j + 1).compareTo(data.get(j)) > 0)
                    j++;
                // data[j] 是 leftChild 和 rightChild 中的最大值
    
                if (data.get(k).compareTo(data.get(j)) >= 0)
                    break;
    
                data.swap(k, j);
                k = j;
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]

# 取出最大元素后，放入一个新的元素 Replace #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]

// 取出堆中的最大元素，并且替换成元素e
        public E replace(E e) { 
            E ret = findMax();
            data.set(0, e);
            siftDown(0);
            return ret;
        }

# 将任意数组整理成堆的形状 Heapify #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]

public MaxHeap(E[] arr) { 
            data = new Array<E>(arr);
            for (int i = parent(arr.length - 1); i >= 0; i--)
                siftDown(i);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/2817dfa148fd439ea427c55710f8136e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/bde6d8303a3b40d287839c93be5cb8be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/bd79e69068564e64832f92752a9303eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/388ae8132f544f4399747a1799d3ec75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/c5045326ea6e428080db14968961677d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/89f046dc0ca24054b47531441fa614f1.png