精华内容
下载资源
问答
  • C++二叉堆binary heap (附完整源码)
    2021-03-09 09:03:49

    二叉堆binary heap 算法的完整源码(定义,实现,main函数测试)

    #include <climits>
    #include <iostream>
    #include <utility>
    
    /** A class for Min Heap */
    class MinHeap {
       
        
    更多相关内容
  • 二叉堆(Binary Heap) 获取最大值 最大堆 - 添加 添加过程总结 最大堆 — 添加优化 最大堆 - 删除 replace(替换堆顶的元素) 最大堆 — 批量建堆(Heapify) 自上而下的上滤 自下而上的下滤 效率对比 ...

    目录

    堆(Heap)

    堆的基本接口设计

    二叉堆(Binary Heap)

    获取最大值

    最大堆 - 添加

    添加过程总结

    最大堆 — 添加优化

    最大堆 - 删除

    replace(替换堆顶的元素)

    最大堆 — 批量建堆(Heapify)

    自上而下的上滤

    自下而上的下滤

    效率对比

    二叉堆源码

    堆的基本接口 Heap.java

    抽象类 AbstractHeap.java

    二叉堆 BinaryHeap.java

    构建一个最小堆

    TOP K 问题

    【引出堆】

    • 堆   获取最大值:O(1)、删除最大值:O(logn)、添加元素:O(logn)
       

    【Top K问题】

    • 什么是TopK问题
      • 从海量数据中找出前K个数据
    • 比如
      • 从100万个整数中找出最大的100个整数
    • TopK问题的解法之一:可以用数据结构“堆”来解决

    堆(Heap)

    (Heap)是一种 树状 的数据结构,常见的堆实现有

    • 二叉堆(Binary Heap,完全二叉堆
    • 多叉堆(D-heap、D-ary Heap)
    • 索引堆(Index Heap)
    • 二项堆(Binomial Heap)
    • 斐波那契堆(Fibonacci Heap)
    • 左倾堆(Leftist Heap,左式堆
    • 斜堆(Skew Heap)
    • 堆的重要性质:任意节点的值总是 ≥( ⩽) 子节点的值
      • 如果任意节点的值总是 ≥ 子节点的值,称为:最大堆、大根堆、大顶堆
      • 如果任意节点的值总是 ⩽ 子节点的值,称为:最小堆、小根堆、小顶堆
    • 堆中的元素必须具备可比较性(跟二叉搜索树一样)

    堆的基本接口设计

    二叉堆(Binary Heap)

    • 二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆
    • 鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可

    • 使用数组存放

    【索引 i 的规律(n 是元素数量)】

    获取最大值

    • 注意检测数组不能为空
    public E get() {
    	emptyCheck();
    	return elements[0];
    }
    private void emptyCheck() {
    	if (size == 0) {
    		throw new IndexOutOfBoundsException("Heap is empty");
    	}
    }

    最大堆 - 添加

    • 添加一个新元素80

    • 和父节点进行交换

    • 进行循环比较,交换

    添加过程总结

    • 代码实现

    /**
     * 最大堆 — 添加
     */
    public void add(E element) {
    	// 检测传入的元素非空
    	elementNotNullCheck(element);
    	// 扩容操作,确保容量大于当前元素个数大小
    	ensureCapacity(size + 1);
    	// 将要添加的元素放到数组最后
    	elements[size++] = element;
    	// 上滤操作
    	siftUp(size - 1);
    }
    /**
     * 让index位置的元素上滤
     */
    private void siftUp(int index) {
    	E e = elements[index]; // 要添加的节点
    	while (index > 0) { // 直到比较到根结点
    		int pindex = (index - 1) >> 1; // 父节点索引
    		E p = elements[pindex]; // 添加节点的父节点
    		if (compare(e, p) <= 0) return;
    		
    		// 交换index、pindex位置的内容
    		E tmp = elements[index];
    		elements[index] = elements[pindex];
    		elements[pindex] = tmp;
    		
    		// 重新赋值index
    		index = pindex;
    	}
    }

    最大堆 — 添加优化

    /**
     * 让index位置的元素上滤
     */
    private void siftUp(int index) {
    	E element = elements[index];
    	while (index > 0) {
    		// 父节点索引 = (子节点索引-1) / 2
    		int parentIndex = (index - 1) >> 1;
    		E parent = elements[parentIndex];
    		if (compare(element, parent) <= 0) break;
    		
    		// 将父元素存储在index位置
    		elements[index] = parent;
    		
    		// 重新赋值index
    		index = parentIndex;
    	}
    	elements[index] = element;
    }

    最大堆 - 删除

    /**
     * 最大堆—删除堆顶元素
     */
    public E remove() {
    	// 检测数组不能为空
    	emptyCheck(); 
    	// 获取数组最后元素的索引
    	int lastIndex = --size;
    	// 获取要删除元素的节点
    	E root = elements[0];
    	elements[0] = elements[lastIndex];
    	elements[lastIndex] = null;
    	
    	siftDown(0); // 下滤操作
    	return root;
    }
    /**
     * 让index位置的元素下滤
     */
    private void siftDown(int index) {
    	E element = elements[index];
    	int half = size >> 1; // 非叶子节点的数量
    	// 第一个叶子节点的索引 == 非叶子节点的数量
    	// index < 第一个叶子节点的索引
    	// 必须保证index位置是非叶子节点
    	while (index < half) { 
    		// index的节点有2种情况
    		// 1.只有左子节点
    		// 2.同时有左右子节点
    		
    		// 默认为左子节点跟它进行比较
    		int childIndex = (index << 1) + 1;
    		E child = elements[childIndex];
    		
    		// 右子节点
    		int rightIndex = childIndex + 1;
    		
    		// 选出左右子节点最大的那个
    		if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
    			child = elements[childIndex = rightIndex];
    		}
    		
    		if (compare(element, child) >= 0) break;
    
    		// 将子节点存放到index位置
    		elements[index] = child;
    		// 重新设置index
    		index = childIndex;
    	}
    	elements[index] = element;
    }

    replace(替换堆顶的元素)

    public E replace(E element) {
    	elementNotNullCheck(element);
    	
    	E root = null;
    	if (size == 0) {
    		elements[0] = element;
    		size++;
    	} else {
    		root = elements[0];
    		elements[0] = element;
    		siftDown(0);
    	}
    	return root;
    }

    最大堆 — 批量建堆(Heapify)

    • 自上而下的上滤
    • 自下而上的下滤

    自上而下的上滤

    自下而上的下滤

    效率对比

    • 自上而下的上滤时间复杂度:O ( n l o g n ) O(nlogn)O(nlogn)
    • 自下而上的下滤时间复杂度:O ( n l o g k ) O(nlogk)O(nlogk)

    二叉堆源码

    堆的基本接口 Heap.java

    public interface Heap<E> {
    	int size();	// 元素的数量
    	boolean isEmpty();	// 是否为空
    	void clear();	// 清空
    	void add(E element);	 // 添加元素
    	E get();	// 获得堆顶元素
    	E remove(); // 删除堆顶元素
    	E replace(E element); // 删除堆顶元素的同时插入一个新元素
    }

    抽象类 AbstractHeap.java

    @SuppressWarnings("unchecked")
    public abstract class AbstractHeap<E> implements Heap<E> {
    	protected int size;
    	protected Comparator<E> comparator;
    	
    	public AbstractHeap(Comparator<E> comparator) {
    		this.comparator = comparator;
    	}
    	
    	public AbstractHeap() {
    		this(null);
    	}
    	
    	@Override
    	public int size() {
    		return size;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return size == 0;
    	}
    	
    	protected int compare(E e1, E e2) {
    		return comparator != null ? comparator.compare(e1, e2) 
    				: ((Comparable<E>)e1).compareTo(e2);
    	}
    }

    二叉堆 BinaryHeap.java

    /**
     * 二叉堆(最大堆)
     */
    @SuppressWarnings("unchecked")
    public class BinaryHeap<E> extends AbstractHeap<E> {
    	private E[] elements;
    	private static final int DEFAULT_CAPACITY = 10;
    	
    	public BinaryHeap(E[] elements, Comparator<E> comparator)  {
    		super(comparator);
    		
    		if (elements == null || elements.length == 0) {
    			this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    		} else {
    			size = elements.length;
    			int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
    			this.elements = (E[]) new Object[capacity];
    			for (int i = 0; i < elements.length; i++) {
    				this.elements[i] = elements[i];
    			}
    			heapify();
    		}
    	}
    	
    	public BinaryHeap(E[] elements)  {
    		this(elements, null);
    	}
    	
    	public BinaryHeap(Comparator<E> comparator) {
    		this(null, comparator);
    	}
    	
    	public BinaryHeap() {
    		this(null, null);
    	}
    
    	@Override
    	public void clear() {
    		for (int i = 0; i < size; i++) {
    			elements[i] = null;
    		}
    		size = 0;
    	}
    
    	@Override
    	public void add(E element) {
    		elementNotNullCheck(element);
    		ensureCapacity(size + 1);
    		elements[size++] = element;
    		siftUp(size - 1);
    	}
    
    	@Override
    	public E get() {
    		emptyCheck();
    		return elements[0];
    	}
    
    	/**
    	 * 删除堆顶元素
    	 */
    	public E remove() {
    		emptyCheck();
    		
    		int lastIndex = --size;
    		E root = elements[0];
    		elements[0] = elements[lastIndex];
    		elements[lastIndex] = null;
    		
    		siftDown(0);
    		return root;
    	}
    
    	@Override
    	public E replace(E element) {
    		elementNotNullCheck(element);
    		
    		E root = null;
    		if (size == 0) {
    			elements[0] = element;
    			size++;
    		} else {
    			root = elements[0];
    			elements[0] = element;
    			siftDown(0);
    		}
    		return root;
    	}
    	
    	/**
    	 * 批量建堆
    	 */
    	private void heapify() {
    		// 自上而下的上滤
    //		for (int i = 1; i < size; i++) {
    //			siftUp(i);
    //		}
    		
    		// 自下而上的下滤
    		for (int i = (size >> 1) - 1; i >= 0; i--) {
    			siftDown(i);
    		}
    	}
    	
    	/**
    	 * 让index位置的元素下滤
    	 * @param index
    	 */
    	private void siftDown(int index) {
    		E element = elements[index];
    		int half = size >> 1; // 非叶子节点的数量
    		// 第一个叶子节点的索引 == 非叶子节点的数量
    		// index < 第一个叶子节点的索引
    		// 必须保证index位置是非叶子节点
    		while (index < half) { 
    			// index的节点有2种情况
    			// 1.只有左子节点
    			// 2.同时有左右子节点
    			
    			// 默认为左子节点跟它进行比较
    			int childIndex = (index << 1) + 1;
    			E child = elements[childIndex];
    			
    			// 右子节点
    			int rightIndex = childIndex + 1;
    			
    			// 选出左右子节点最大的那个
    			if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
    				child = elements[childIndex = rightIndex];
    			}
    			
    			if (compare(element, child) >= 0) break;
    
    			// 将子节点存放到index位置
    			elements[index] = child;
    			// 重新设置index
    			index = childIndex;
    		}
    		elements[index] = element;
    	}
    	
    	/**
    	 * 让index位置的元素上滤
    	 */
    	private void siftUp(int index) {
    //		E e = elements[index];
    //		while (index > 0) {
    //			int pindex = (index - 1) >> 1;
    //			E p = elements[pindex];
    //			if (compare(e, p) <= 0) return;
    //			
    //			// 交换index、pindex位置的内容
    //			E tmp = elements[index];
    //			elements[index] = elements[pindex];
    //			elements[pindex] = tmp;
    //			
    //			// 重新赋值index
    //			index = pindex;
    //		}
    		E element = elements[index];
    		while (index > 0) {
    			// 父节点索引 = (子节点索引-1) / 2
    			int parentIndex = (index - 1) >> 1;
    			E parent = elements[parentIndex];
    			if (compare(element, parent) <= 0) break;
    			
    			// 将父元素存储在index位置
    			elements[index] = parent;
    			
    			// 重新赋值index
    			index = parentIndex;
    		}
    		elements[index] = element;
    	}
    	
    	private void ensureCapacity(int capacity) {
    		int oldCapacity = elements.length;
    		if (oldCapacity >= capacity) return;
    		
    		// 新容量为旧容量的1.5倍
    		int newCapacity = oldCapacity + (oldCapacity >> 1);
    		E[] newElements = (E[]) new Object[newCapacity];
    		for (int i = 0; i < size; i++) {
    			newElements[i] = elements[i];
    		}
    		elements = newElements;
    	}
    	
    	private void emptyCheck() {
    		if (size == 0) {
    			throw new IndexOutOfBoundsException("Heap is empty");
    		}
    	}
    	
    	private void elementNotNullCheck(E element) {
    		if (element == null) {
    			throw new IllegalArgumentException("element must not be null");
    		}
    	}
    }

    构建一个最小堆

    • 在写完最大堆以后,实现最小堆不需要修改源代码,只需要在创建堆时,传入与最大堆比较方式相反的比较器即可。
    public static void main(String[] args) {
    	Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    	BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
    		public int compare(Integer o1, Integer o2) {
    			return o2 - o1; // 与最大堆比较方式相反
    		}
    	});
    }

    TOP K 问题

    public static void main(String[] args) {
    	// 新建一个小顶堆
    	BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
    		public int compare(Integer o1, Integer o2) {
    			return o2 - o1;
    		}
    	});
    	
    	// 找出最大的前k个数
    	int k = 3;
    	Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93, 
    			91, 19, 54, 47, 73, 62, 76, 63, 35, 18, 
    			90, 6, 65, 49, 3, 26, 61, 21, 48};
    	for (int i = 0; i < data.length; i++) {
    		if (heap.size() < k) { // 前k个数添加到小顶堆
    			heap.add(data[i]); // logk
    		} else if (data[i] > heap.get()) { // 如果是第 k + 1 个数,并且大于堆顶元素
    			heap.replace(data[i]); // logk
    		}
    	}
    	// O(nlogk)
    }
    • 如果是找出最小的前 k 个数呢?
      • 用大顶堆
      • 如果小于堆顶元素,就使用 replace 操作。
    展开全文
  • 本文欢迎转载,转载前请联系作者。...二叉堆(binary heap)是一种通常用于实现优先队列的数据结构。要想知道二叉堆是什么东西,得从两方面介绍它:结构性和堆序性。 1.结构性 二叉堆是一颗除底层...

    本文欢迎转载,转载前请联系作者。若未经允许转载,转载时请注明出处,谢谢! http://blog.csdn.net/colton_null 作者:喝酒不骑马 Colton_Null from CSDN


    一.什么是二叉堆?

    二叉堆(binary heap)是一种通常用于实现优先队列的数据结构。要想知道二叉堆是什么东西,得从两方面介绍它:结构性和堆序性。

    1.结构性

    二叉堆是一颗除底层外被完全填满的二叉树,对于底层上的元素满足从左到右填入的特性。如下图所示。
    这里写图片描述
    所以,鉴于二叉堆的这个结构特性,我们可以很容易得出——一颗高为h的二叉堆有 2 h 2^h 2h 2 h + 1 − 1 2^{h+1} - 1 2h+11 个节点。

    而且,基于二叉堆的这个特性,我们可以用一个数组在表示这种数据结构,不需要使用链。如下图所示。
    这里写图片描述

    数组上任意位置i上的元素,它的左节点在2i上,右节点在2i + 1上,它的父节点在└i/2┘。不用链表的好处在于,这么做对于计算机来说,访问某一元素的效率很高,不需要遍历即可访问。

    2.堆序性

    这里我们用最小堆(min-heap)来说明。

    在堆中,每个节点n,都小于或等于它的两个子节点。如下图所示。
    这里写图片描述
    当然,我们可以类比处最大堆(max-heap)即每个节点都大于或等于它的子节点。

    根据二叉堆的这个性质,最小元素或者最大元素即为根节点。我们直接就可以访问到这个最小的元素,即array[1](数组结构参考结构性)。

    二.保持二叉堆的特性

    在使用二叉堆的时候,我们对二叉堆插入和获取最小值的操作,会破坏二叉堆的特性。那么我们需要在每次操作之后,对二叉堆进行维护。

    1.上滤

    我们在执行插入(insert)操作的时候,可以采用上滤(percolate up)策略对二叉树进行维护。

    首先在插入元素t时,在底层创建一个空穴,以保证完全二叉树的性质。如果元素t可以直接放在该空穴中不影响堆的堆序性,则插入完成;如果元素t不能直接放置在空穴中(即对于min-heap来说,t小于它的根节点或对于max-heap来说,t大于它的根节点),则把空穴的根节点放置在空穴中,原根节点被视为空穴。直到t被放入在合适的空穴中。

    过程如下图所示,插入元素18。
    这里写图片描述

    2.下滤

    在我们获取最小元素(即获取根节点并删除它时),我们需要用下滤(percolate down)策略来维护堆序性。

    当删除最小元素时,根节点变为空穴,那么为了保证二叉堆的结构性,所以要把最后一个元素x移动到该堆的某个地方。如果x可以直接放入到空穴中,则下滤结束;否则,空穴子节点中最小或最大的值(这要看是min-heap还是max-heap,min-heap为最小值,max-heap为最大值)放入到空穴中,然后空穴下移一位,直到x可以被放置在空穴中。

    过程如下图所示。

    这里写图片描述

    3.最小二叉堆的Java实现

    BinaryHeap.java

    public class BinaryHeap<T extends Comparable<? super T>> {
        public BinaryHeap() {
            this(DEFAULT_CAPACITY);
        }
    
        public BinaryHeap(int capacity) {
            currentSize = 0;
            arr = (T[]) new Comparable[capacity + 1];
        }
    
        public BinaryHeap(T[] items) {
            currentSize = items.length;
            arr = (T[]) new Comparable[(currentSize + 2) * 11 / 10];
    
            int i = 1;
            for (T item : items) {
                arr[i++] = item;
            }
            buildHeap();
        }
    
        /**
         * 二叉堆的插入方法。使用上滤法。
         *
         * @param t 被插入的元素
         */
        public void insert(T t) {
            if (currentSize == arr.length - 1) {
                // 如果当前元素个数为数组长度-1,则扩容
                enlargeArray(arr.length * 2 + 1);
            }
            int hole = ++currentSize;
            // arr[0] = t初始化,最后如果循环到顶点,t.compartTo(arr[hole / 2])即arr[0]为0,循环结束
            for (arr[0] = t; t.compareTo(arr[hole / 2]) < 0; hole /= 2) {
                // 根节点的值赋值到子节点
                arr[hole] = arr[hole / 2];
            }
            // 根节点(或树叶节点)赋值为t
            arr[hole] = t;
        }
    
        /**
         * 寻找堆内最小值。索引1处的元素最小。
         *
         * @return
         */
        public T findMin() {
            if (isEmpty()) {
                // 这里如果堆为空,可以抛出异常。
                // throw new UnderflowException( );
            }
            // 第1位的元素最小
            return arr[1];
        }
    
        public T deleteMin() {
            if (isEmpty()) {
                // 这里如果堆为空,可以抛出异常。
                // throw new UnderflowException( );
            }
            T minItem = findMin();
            // 将最后一个节点赋值到根节点
            arr[1] = arr[currentSize--];
            // 从根节点执行下滤
            percolateDown(1);
            return minItem;
        }
    
        /**
         * 判断堆是否为空
         *
         * @return 为空返回true;否则返回false
         */
        public boolean isEmpty() {
            return currentSize == 0;
        }
    
        /**
         * 堆置空
         */
        public void makeEmpty() {
            currentSize = 0;
        }
    
        /**
         * 打印堆
         */
        public void print(){
            System.out.print("堆为:");
            for (int i = 1;arr[i] != null;i++){
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        private static final int DEFAULT_CAPACITY = 10;
    
        private int currentSize;
        private T[] arr;
    
        /**
         * 下滤
         *
         * @param hole 下滤其实的节点的索引
         */
        private void percolateDown(int hole) {
            int child;
            T tmp = arr[hole];
    
            for (; hole * 2 <= currentSize; hole = child) {
                child = hole * 2;
                if (child != currentSize && arr[child + 1].compareTo(arr[child]) < 0) {
                    // 做子节点不为左后一个节点(说明有右节点)且右节点比做节点小,索引改为右节点节点
                    child++;
                }
                if (arr[child].compareTo(tmp) < 0) {
                    // 如果遍历到的这个节点比最后一个元素小
                    arr[hole] = arr[child];
                } else {
                    break;
                }
            }
            // 将最后一个元素补到前面的空位
            arr[hole] = tmp;
        }
    
        private void buildHeap() {
            for (int i = currentSize / 2; i > 0; i--) {
                percolateDown(i);
            }
        }
    
        /**
         * 扩容
         * @param newSize 新数组的大小
         */
        private void enlargeArray(int newSize) {
            T[] old = arr;
            arr = (T[]) new Comparable[newSize];
            for (int i = 0; i < old.length; i++) {
                arr[i] = old[i];
            }
        }
    }
    

    BinaryHeapTest.java 测试类

    public class BinaryHeapTest {
        public static void main(String[] args) {
            BinaryHeap binaryHeap = new BinaryHeap();
            int[] nums = new int[]{23, 98, 34, 63, 3, 0, 87, 45};
            for (Integer num : nums) {
                binaryHeap.insert(num);
            }
            binaryHeap.print();
    
            System.out.println("堆是否为空:" + binaryHeap.isEmpty());
    
    
            System.out.println("获取最小值:" + binaryHeap.deleteMin());
    
            binaryHeap.print();
    
        }
    }
    

    输出:

    堆为:0 23 3 45 63 34 87 98 
    堆是否为空:false
    获取最小值:0
    堆为:3 23 34 45 63 98 87 98 
    

    最小二叉堆实现可用。

    以上就是有关二叉堆(binary heap)介绍及其Java实现。


    有关[数据结构与算法]的学习内容已经上传到github,喜欢的朋友可以支持一下。
    data-structures-and-algorithm-study-notes-java


    站在前人的肩膀上前行,感谢以下博客及文献的支持。
    《数据结构与算法分析(第3 版) 工业出版社》

    展开全文
  • 本篇文章将简要解释什么是二叉堆以及二叉堆的Python实现什么是二叉堆(binary heap)实现思路(以最大堆为例)通过上浮操作来向堆中新增元素通过下沉操作来取出堆中元素数据结构设计&封装实现 什么是二叉堆(binary...

    什么是二叉堆(binary heap)

    二叉堆是一种满足特殊性质的二叉树。具有以下性质:

    1. 二叉堆是一颗完全二叉树(除叶子节点以外其余节点的左右孩子都不为空)
    2. 所有节点的值都大于等于(最大堆)孩子节点的值最小堆刚好相反
      二叉堆在排序和求取top N 等问题上都有广泛的应用

    实现思路(以最大堆为例)

    因为堆是一颗完全二叉树,所以采用 列表 + shift_up + shift_down 的经典方式实现堆会很容易
    用列表实现堆可以方便的发现:

    1. 一个节点 p索引为pi 的左孩子索引 li = pi * 2 + 1
    2. 一个节点 p索引为pi 的右孩子索引 ri = pi * 2 + 2
    3. 一个节点 p索引为pi 的父亲索引 parent_i = (pi - 1) // 2 (向下取整)
      所以我们可以很方便的封装出获取一个节点的左右孩子和父亲节点的方法
    class MaxHeap(object):
    
        def __init__(self):
            self.data = []
    
        def __left_child(self, index):
            return index * 2 + 1
    
        def __right_child(self, index):
            return index * 2 + 2
    
        def __parent(self, index):
            if index == 0:
                raise Exception('堆顶没有父亲节点')
            else:
                return (index - 1) // 2
    

    通过上浮操作来向堆中新增元素

    上浮操作就是指每次新增元素的时候将新增元素放入数组末尾,之后通过索引获取新增节点的父亲节点的索引,如果新增节点的数值比父亲节点的数值大,就将新增节点的值和父亲节点进行交换,即是上浮,不断上浮直到到堆顶整个新增操作完成,封装上浮操作如下

    class MaxHeap(object):
        ......
        def __shift_up(self, index):
            while index > 0 and self.data[index] > self.data[self.__parent(index)]:
                self.data[index], self.data[self.__parent(index)] = self.data[self.__parent(index)], self.data[index]
                index = self.__parent(index)
    

    通过下沉操作来取出堆中元素

    下沉操作就是为了保证取出堆顶元素之后,其余元素可以组成新的最大堆:

    1. 将堆顶元素和堆尾元素进行互换,弹出堆尾元素作为返回
    2. 从堆顶开始 和其左右孩子中较大的孩子进行比较,如果比左右孩子中较大的孩子要小,就与左右孩子中较大的孩子进行互换不断下沉,直到比左右孩子中较大的元素要大的时候(堆的第二个性质),新的最大堆就形成了,下沉操作完成
      这里注意判断一个节点是否有左右孩子,防止数组越界
    class MaxHeap(object):
        ......
        def __shift_down(self, index):
        	# 先判断是否有左孩子
            while self.__left_child(index) < len(self.data):
                li = self.__left_child(index)
                lr = self.__right_child(index)
    			# 再判断是否有右孩子
                if lr < len(self.data) and self.data[li] < self.data[lr]:
                    j = lr
                else:
                    j = li
    
                if self.data[index] < self.data[j]:
                    self.data[index], self.data[j] = self.data[j], self.data[index]
                    index = j
                else:
                    break
    

    数据结构设计&封装

    1. def add(word) // return None 向Trie中添加一个单词
    2. def is_empty() // return bool 询问字典树是否包含该前缀的单词
    3. def size() // ruturn int 返回字典树存储单词个数 使用__len__()代替
    4. def extract_max() // return e 弹出堆顶元素
    5. def find_max() // return e 查看堆顶元素
    6. def heapify(arr) // return None 将数组序列化为堆
    7. def replace(e) // return e 替换堆顶元素
      为了保证Python语法风格,使用魔法函数实现部分功能

    实现

    class MaxHeap(object):
    
        def __init__(self, heapify = None):
            if heapify:
                self.heapify(heapify)
            else:
                self.data = []
    
        def __len__(self):
            return len(self.data)
    
        def is_empty(self):
            return len(self.data) == 0
    
        def __left_child(self, index):
            return index * 2 + 1
    
        def __right_child(self, index):
            return index * 2 + 2
    
        def __parent(self, index):
            if index == 0:
                raise Exception('堆顶没有父亲节点')
            else:
                return (index - 1) // 2
    
        def add(self, e):
            self.data.append(e)
            self.__shift_up(len(self.data) - 1)
    
        def __shift_up(self, index):
            while index > 0 and self.data[index] > self.data[self.__parent(index)]:
                self.data[index], self.data[self.__parent(index)] = self.data[self.__parent(index)], self.data[index]
                index = self.__parent(index)
    
        def extract_max(self):
            if self.is_empty():
                self.data[0], self.data[-1] = self.data[-1], self.data[0]
                res = self.data.pop()
    
                self.__shift_down(0)
                return res
            else:
                raise Exception('堆为空')
    
    
        def find_max(self):
            if self.is_empty():
                raise Exception('堆为空')
    
            return self.data[0]
    
        def __shift_down(self, index):
            while self.__left_child(index) < len(self.data):
                li = self.__left_child(index)
                lr = self.__right_child(index)
    
                if lr < len(self.data) and self.data[li] < self.data[lr]:
                    j = lr
                else:
                    j = li
    
                if self.data[index] < self.data[j]:
                    self.data[index], self.data[j] = self.data[j], self.data[index]
                    index = j
                else:
                    break
    
        def replace(self, e):
            res = self.data[0]
            self.data[0] = e
            self.__shift_down(0)
            return res
    
        def heapify(self, arr):
            self.data = arr
            pi = self.__parent(len(arr) - 1)
    
            while pi >= 0:
                self.__shift_down(pi)
                pi -= 1
    

    转载注明出处

    展开全文
  • 数据结构之Binary Heap(二叉堆)

    千次阅读 2016-10-22 15:11:50
    数据结构之Binary Heap(二叉堆)1.Binary Heap的定义 二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何...
  • binary heap

    2019-09-27 03:58:18
    Incomputer science, aheapis a specializedtree-baseddata structurethat satisfies theheap property:If A is a parentnodeof B then the key of node A is ordered with respect to the key of nod...
  • 1.堆 Heap 定义:可以迅速找到一堆数中的最大值或者最小值的数据结构。 应用场景:经常是一个数一个数的过来,比如找最大值或者找最小值 分类:堆本身是一个抽象的数据结构,根据实现形式,将其分为二叉堆、斐波那契...
  • binary heap(array based)

    2017-01-11 15:47:59
    Head file: ...#ifndef _BINARY_HEAP_ #define _BINARY_HEAP_ #include #include #include #include #include using namespace std; template class BinaryHeap { public: BinaryHeap() = defau
  • Binary Heap

    2015-11-05 21:58:40
    Priority Queue & Heap
  • 二叉堆(binary heap)

    2017-10-06 22:46:27
    本人做的一个二叉堆的课件,附带STL中的priority_queue
  • 二叉堆 Binary Heap

    2021-01-11 15:15:10
    二叉堆 Binary HeapBinary Heap的基本概念Binary Heap的核心原理siftUpsiftDownBinary Heap的基本方法HeapifyPushPopBinary Heap的时间复杂度Binary Heap的实现Heap InterfaceHeap AbstractMax HeapMin Heap Binary ...
  • 二叉堆(Binary Heap) (1)structure property Heap(堆)是一个除了底层节点外的完全填满的二叉树,底层可以不完全,左到右填充节点。(a heap is a binary tree that completely filled, with the exception ...
  • heap->heap_size = 0; heap->data[0] = MINDATA; return heap; } void makeEmpty(BinHeap h) { if (h) { h->heap_size = 0; } } void destroy(BinHeap h) { if (h) { if (h->data) { free(h->data)...
  • Binary Heap(二叉堆)

    2017-02-10 13:24:28
    Binary Heap(二叉堆) 在计算机科学中,二叉堆是二叉树形状的堆结构。二叉堆是最常见的实现优先级队列的方法,它与优先级队列紧密相连,一起应用到诸多地方,在很多主流语言的标准算法库中都能看到它们的身影。同时...
  • 2.Binary Heap[数据结构]

    2017-11-30 22:52:28
    A Binary Heap is a Binary Tree with following properties. 1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible...
  • C++之Binary Heap/Max Heap

    2017-05-17 22:36:00
    1 #include <iostream> 2 #include <time.h> 3 #include <random> 4 5 using namespace std;... 7 //Binary Heap; Max Heap; 8 9 class BinaryHeap 10 { 11 ...
  • STL 简单 binary heap 的实现

    千次阅读 2016-05-22 21:56:24
     所谓binary heap就是一种完全二叉树,也就是说,整颗binary tree除了对底层的叶节点外,是填满的,而最底层的叶节点由左至右不能有空隙。  完全二叉树内没有任何节点漏洞,这带来一个极大的好处:我们可以利用...
  • 二叉堆(Binary Heap)本质上是一种完全二叉树,它分为:最大堆、最小堆。 二叉堆的特征: 最大堆:任何一个父节点的值,都大于等于它左右孩子节点的值。 最小堆:任何一个父节点的值,都小于等于它左右孩子节点...
  • 该数据结构表示为保留min-heap属性的二叉树; 也就是说,每个节点的优先级都大于其父节点的优先级。 它对于堆排序的实现很有用,在这种排序中,将无序项目的数组加载到BinaryHeap中,并且最小优先级元素被重复删除...
  • Binary heap

    2017-12-25 13:44:51
    package heap; import java.util.ArrayList; import java.util.List; /** * 二叉堆(最大堆)优先队列的实现 * 堆是一颗被完全填满的二叉树(最底层除外 * Created by long.chen on 2017/12/25. */ public ...
  • 基本介绍堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;这种数据结构具有以下性质。 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。 堆总是一棵完全树。即除了最底层...
  • 优先队列-二叉堆(Binary Heap) 为了方便自己进行修改,这里放上我的为知笔记的外链: http://7c0bab95.wiz03.com/share/s/1Y2WKl218k5e2gpBCl2BeEsq2ycx9z1l0k8e2UO19E1L0B0u
  • 使操作被快速执行的性质是堆序(heap order)性. 由于我们想要快速地找出最小元,因此最小元应该在根上. 类似的,可以声明一个max堆,找到和删除最大元 在一个堆中,对于每一个节点X,X的parent中的关键字<=X中...
  • 看动画学算法之:二叉堆Binary Heap

    千次阅读 2020-09-01 11:11:44
    我们坐在高高的谷堆旁边,听妈妈讲那过去的事情。听到了堆,我就想起了这首歌。 没错,今天我们要介绍一个堆,这个堆叫做二叉堆。 二叉树我们之前讲过了,就是每个节点...而二叉堆Binary Heap是一种特殊的二叉树。
  • 二叉堆因为对应着一棵完全二叉树,因而可以通过线性数组的方式实现。 注意,数组第 0 个位置上的元素,作为根,还是第 1 个位置上的元素作为根?本文给出的实现,以数组第 1 个位置上的元素作为根,则其两个孩子 ⇒ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,722
精华内容 11,088
关键字:

binary heap