精华内容
下载资源
问答
  • 堆是一种特殊的“队列”,它取出元素的顺序是依照元素的优先级大小,而不是元素进入...根据最小堆的结构特性,本文使用含有哨兵元素的数组实现了最小堆的创建、插入和删除。 数据类型定义和函数声明 #include #

    堆是一种特殊的“队列”,它取出元素的顺序是依照元素的优先级大小,而不是元素进入队列的先后顺序。堆具有两个特性,1.结构性:它是能用数组表示的完全二叉树。2.堆序性:任一结点的关键字是其子树所有结点的最大值(最大堆)或最小值(最小堆),即任意子树也应该是个堆。

    根据最小堆的结构特性,本文使用含有哨兵元素的数组实现了最小堆的创建、插入和删除。

    数据类型定义和函数声明

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MinData -100//哨兵元素的值
    typedef struct HeapStruct{
    	int *p;
    	int size;
    	int capacity;
    } *MinHeap;
    
    MinHeap Init_MinHeap(int MaxSize);
    int IsFull(MinHeap H);
    int IsEmpty(MinHeap H);
    void Insert(MinHeap H, int data);
    int Delete(MinHeap H);
    void BuildMinHeap(MinHeap H, int N);
    void PrintValue(MinHeap H);
    

    程序中用到的功能函数

    int IsFull(MinHeap H)
    {
    	return (H->size == H->capacity) ? 1 : 0;
    }
    
    int IsEmpty(MinHeap H)
    {
    	return (H->size == 0) ? 1 : 0;
    }
    
    void PrintValue(MinHeap H)
    {
    	int i;
    	printf("最小堆中的元素依次为:");
    	for (i = 1; i <= H->size; i++)
    		printf("%d ", H->p[i]);
    	printf("\n");
    }

    最小堆的初始化

    该函数给最小堆分配了内存空间并完成初始化操作,此时最小堆中元素为空。

    MinHeap Init_MinHeap(int MaxSize)
    {
    	MinHeap H = (MinHeap)malloc(sizeof(HeapStruct));
    	H->p = (int*)malloc((MaxSize + 1) * sizeof(int));
    	H->p[0] = MinData;
    	H->size = 0;
    	H->capacity = MaxSize;
    	return H;
    }

    在最小堆中插入元素

    插入元素的关键是把要插入的元素放在最小堆的合适位置中。所谓合适即不破坏最小堆的结构性和堆序性。

    为了将一个元素data插入到堆中,在遵守堆的结构性特点(完全二叉树)基础上,在下一个空闲位置创建一个空穴。如果元素data可以放在该空穴中而并不破坏堆的序,则完成插入。否则,把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着根的方向上移动一层。继续该过程知道元素data能放入空穴中。因为空穴在逐渐往树的上方移动,所以把这种策略成为“上滤”。

    void Insert(MinHeap H, int data)
    {
    	int i;
    	if (IsFull(H))
    	{
    		printf("最小堆已满,无法插入元素");
    		return;
    	}
    	for (i = ++H->size; data < H->p[i / 2]; i /= 2)
    		H->p[i] = H->p[i / 2];
    	H->p[i] = data;
    }

    删除最小堆中的最小元素

    删除元素的关键是把堆中最后一个元素移动到最小堆中的合适位置。所谓合适即不破坏最小堆的结构性和堆序性。

    删除元素以类似于插入的方式处理。找到最小元很容易(第一个元素),困难的部分是删除后的调整。当删除一个最小元时,在根节点处产生一个空穴。由于现在堆里少了一个元素,因为堆中最后一个元素lastvalue必须移动到该堆的某个地方。通常我们将空穴的两个儿子中较小者移入空穴,这样就把空穴向下退了一层。重复该步骤知道lastvalue可以放在空穴中。通常把这种策略成为“下滤”。

    int Delete(MinHeap H)
    {
    	int minvalue , lastvalue, child, parent;
    	if (IsEmpty(H))
    	{
    		printf("最小堆已满,无法删除元素");
    		return -999;
    	}
    
    	minvalue = H->p[1];
    	lastvalue = H->p[H->size--];
    	for (parent = 1; 2 * parent <= H->size; parent = child)
    	{
    		child = 2 * parent;/*默认左结点的元素值更小*/
    		if (child != H->size && H->p[child + 1] < H->p[child])/*若右节点的元素值更小,则调整child*/
    			child++;
    		if (lastvalue < H->p[child])
    			break;
    		else
    			H->p[parent] = H->p[child];
    	}
    	H->p[parent] = lastvalue;
    	return minvalue;
    }

    创建最小堆

    在创建最小堆时,可以 : 通过插入操作Insert函数,将N 个元素一个个相继插入到一个初始为空的堆中去 ,但其时间代价最大为O(NlogN)。

    也可以在线性复杂度下建立最小堆,基本步骤为:1. 将N个元素按输入顺序存入,先满足完全二叉树的结构特性。2.调整各节点位置,以满足最大堆的堆序性。这样创建最小堆时的时间代价为O(N)。在调整节点位置时,只需对从第N/2个节点到第一个节点依次应用“下滤”策略即可,其实也就是进行了N/2次的近似删除操作。

    void BuildMinHeap(MinHeap H, int N)
    {
    	int i, num, parent, child, root, lastvalue;
    	if (N > H->capacity)
    	{
    		printf("要创建的元素个数超过堆的最大容量,创建失败");
    		return;
    	}
    	for (i = 1; i <= N; i++)
    	{
    		printf("请输入要插入的元素值:");
    		scanf_s("%d", &num);
    		H->p[i] = num;
    	}
    	H->size = N;
    
    	root = N / 2;/*从第N/2个结点到第1个结点依次进行下滤 近似N/2次删除操作*/
    	while (root)
    	{
    		lastvalue = H->p[root];
    		for (parent = root; 2 * parent <= H->size; parent = child)
    		{
    			child = 2 * parent;/*默认左结点的元素值更小*/
    			if (child != H->size && H->p[child + 1] < H->p[child])/*右结点元素值更小*/
    				child++;
    			if (lastvalue < H->p[child])
    				break;
    			else
    				H->p[parent] = H->p[child];
    		}
    		H->p[parent] = lastvalue;
    		--root;
    	}
    }
    

    主程序

    测试序列:150 80 40 30 10 70 110 100 20 90 60 50 120 140 130

    正确结果为:10 20 40 30 60 50 110 100 150 90 80 70 120 140 130

    void main()
    {
    	int num;
    	MinHeap H;
    	H = Init_MinHeap(100);
    	BuildMinHeap(H, 15);
    	PrintValue(H);
    
    	printf("请输入你要插入的数据:");
    	scanf_s("%d", &num);
    	Insert(H, num);
    	PrintValue(H);
    	printf("请输入你要插入的数据:");
    	scanf_s("%d", &num);
    	Insert(H, num);
    	PrintValue(H);
    
    	num = Delete(H);
    	printf("删除的元素为:%d\n", num);
    	PrintValue(H);
    }


    展开全文
  • 最小堆

    2015-10-19 11:51:07
    最小堆:是指根节点的关键字值是堆中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字最小堆插入操作  步骤: 把待增加的节点编号 i 设置为已知堆的总节点数加 1 ...

    最小堆:是指根节点的关键字值是堆中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字值

    最小堆的插入操作

       步骤:

    1. 把待增加的节点编号 i 设置为已知堆的总节点数加 1 即 i=++(*n),因此,新增的元素放在最下一层作为新的叶子节点。求出节点 i 的父节点 parent=i/2; 判断是否为空堆,并比较所插入元素与父节点关键字值的大小;
    2. 若所插入节点关键字值小于父节点关键字值即item>heap[parent],则把父节点向下移,并把父节点作为当前节点,依次求父节点,即依次沿着树枝向上延伸直到根节点;
    3. 把元素item插入到正确位置;

    最小堆的删除操作

    步骤:   

    首先删除根节点,并把最后一个节点临时作为新的根节点,将新的根节点作为当前节点与其孩子节点中最小的关键值节点进行比较,若大于其孩子节点的关键值,则与其孩子节点进行交换位置,并把新位置作为当前节点继续与其孩子节点进行比较,一直延伸下去,直到没有孩子节点为止;

    libevent中最小堆的实现

    typedef struct min_heap
    {
    struct event** p;
    unsigned n, a;
    } min_heap_t;


    static inline void     min_heap_ctor_(min_heap_t* s);
    static inline void     min_heap_dtor_(min_heap_t* s);
    static inline void     min_heap_elem_init_(struct event* e);
    static inline int     min_heap_elt_is_top_(const struct event *e);
    static inline int     min_heap_empty_(min_heap_t* s);
    static inline unsigned     min_heap_size_(min_heap_t* s);
    static inline struct event*  min_heap_top_(min_heap_t* s);
    static inline int     min_heap_reserve_(min_heap_t* s, unsigned n);
    static inline int     min_heap_push_(min_heap_t* s, struct event* e);
    static inline struct event*  min_heap_pop_(min_heap_t* s);
    static inline int     min_heap_adjust_(min_heap_t *s, struct event* e);
    static inline int     min_heap_erase_(min_heap_t* s, struct event* e);
    static inline void     min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
    static inline void     min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e);
    static inline void     min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);


    #define min_heap_elem_greater(a, b) \
    (evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >))


    void min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
    void min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); }
    void min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
    int min_heap_empty_(min_heap_t* s) { return 0u == s->n; }
    unsigned min_heap_size_(min_heap_t* s) { return s->n; }
    struct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; }


    int min_heap_push_(min_heap_t* s, struct event* e)
    {
    if (min_heap_reserve_(s, s->n + 1))
    return -1;
    min_heap_shift_up_(s, s->n++, e);
    return 0;
    }


    struct event* min_heap_pop_(min_heap_t* s)
    {
    if (s->n)
    {
    struct event* e = *s->p;
    min_heap_shift_down_(s, 0u, s->p[--s->n]);
    e->ev_timeout_pos.min_heap_idx = -1;
    return e;
    }
    return 0;
    }


    int min_heap_elt_is_top_(const struct event *e)
    {
    return e->ev_timeout_pos.min_heap_idx == 0;
    }


    int min_heap_erase_(min_heap_t* s, struct event* e)
    {
    if (-1 != e->ev_timeout_pos.min_heap_idx)
    {
    struct event *last = s->p[--s->n];
    unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
    /* we replace e with the last element in the heap.  We might need to
      shift it upward if it is less than its parent, or downward if it is
      greater than one or both its children. Since the children are known
      to be less than the parent, it can't need to shift both up and
      down. */
    if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
    min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last);
    else
    min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
    e->ev_timeout_pos.min_heap_idx = -1;
    return 0;
    }
    return -1;
    }


    int min_heap_adjust_(min_heap_t *s, struct event *e)
    {
    if (-1 == e->ev_timeout_pos.min_heap_idx) {
    return min_heap_push_(s, e);
    } else {
    unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
    /* The position of e has changed; we shift it up or down
    * as needed.  We can't need to do both. */
    if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e))
    min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e);
    else
    min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e);
    return 0;
    }
    }


    int min_heap_reserve_(min_heap_t* s, unsigned n)
    {
    if (s->a < n)
    {
    struct event** p;
    unsigned a = s->a ? s->a * 2 : 8;
    if (a < n)
    a = n;
    if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
    return -1;
    s->p = p;
    s->a = a;
    }
    return 0;
    }


    void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e)
    {
        unsigned parent = (hole_index - 1) / 2;
        do
        {
    (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
    hole_index = parent;
    parent = (hole_index - 1) / 2;
        } while (hole_index && min_heap_elem_greater(s->p[parent], e));
        (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
    }


    void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
    {
        unsigned parent = (hole_index - 1) / 2;
        while (hole_index && min_heap_elem_greater(s->p[parent], e))
        {
    (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
    hole_index = parent;
    parent = (hole_index - 1) / 2;
        }
        (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
    }


    void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)


    展开全文
  • 插入关键字18,17,15,19】 【插入关键字16,12,21】 【插入关键字27】 【插入关键字13】 【插入关键字11】 插入操作都大同小异。 然后进行删除操作: 【删除关键字】 【删除关键字】 ...

    ok,先上截图:


    下面将演示堆的插入操作


    【插入关键字18,17,15,19】


    【插入关键字16,12,21】


    【插入关键字27】


    【插入关键字13】


    【插入关键字11】




    插入操作都大同小异。



    然后进行删除操作:

    【删除关键字11】


    【删除关键字16】


    【删除关键字13】


    【删除关键字17】


    【删除关键字21】



    ok,我们输入数组进去,然后构建一个最小堆:





    构建完毕后,我们逐个逐个数读取,形成排序完毕的数组(都从根节点开始读,每读一个根节点就删除一个根节点,调整树形结构,直到空):



    下面就是核心代码了:


    package heap;
    
    public class TreeNode {
    public TreeNode parent=null;
    public TreeNode leftChild=null;
    public TreeNode rightChild=null;
    public float key=0.0f;
    public TreeNode rightBrother=null;
    
    public TreeNode leftBrother=null;
    
    }
    



    package heap;
    
    import java.util.ArrayList;
    
    import org.apache.velocity.runtime.directive.Break;
    
    /**
     * 最小堆的实现。---
     * 作者:码农下的天桥。
     * 这个是实现最小堆的核心方法,
     * 也是实现堆排序(从小到大)的核心操作类,
     * 它里面有一个TreeNode作为节点的模型类,各位同学在
     * 看完我摘抄的相关文章及勘误后肯定明白是怎么回事。
     * 至于最大堆------------聪明如你们肯定可以举一反三实现出来的。
     * 
     * */
    
    public class MinTopHeap {
    	
    	private TreeNode _rootNode=null;
    	
    	private ArrayList<Float> _arrContainer=new ArrayList<Float>();
    	
    	public void setRootNode(TreeNode rootNode){
    		_rootNode=rootNode;
    	}
    	public TreeNode getRootNode(){
    		return _rootNode;
    	}
    
    
    
    	public boolean insert(float key) {
    
    		/**
    		 * 假如当前节点为null,那么可以判断是第一次插入关键字,直接插入。
    		 * */
    		if(_rootNode==null){
    			_rootNode=new TreeNode();
    			_rootNode.key=key;
    			_arrContainer.add(key);
    			return true;
    		}
    		/**
    		 * 假如当前为root根节点,并且没有子节点,那么就插入到根节点的左孩子
    		 * */
    		if(_rootNode!=null&&_rootNode.leftChild==null&&_rootNode.rightChild==null){
    			TreeNode cNode=new TreeNode();
    			cNode.key=key;
    			cNode.parent=_rootNode;
    			_rootNode.leftChild=cNode;
    			recursion_adjustment_after_insert(cNode);
    			
    			return true;
    		}
    		/**
    		 * 假如当前为root节点,并且有左子节点,没有右子节点,那么直接添加右子节点。
    		 * */
    		if(_rootNode!=null&&_rootNode.leftChild!=null&&_rootNode.rightChild==null){
    			TreeNode cNode=new TreeNode();
    			cNode.key=key;
    			cNode.parent=_rootNode;
    			_rootNode.rightChild=cNode;
    			
    			_rootNode.leftChild.rightBrother=cNode;
    			cNode.leftBrother=_rootNode.leftChild;
    			recursion_adjustment_after_insert(cNode);
    			
    			return true;
    		}
    		/**
    		 * 假如这些都不是,那么就判断该树形是不是已经满了,满了的话,直接在最左边添加一个左子节点,
    		 * 否则,找出最后的那一个叶子节点,然后判断并添加一个节点。
    		 * */
    		
    		TreeNode cNode=getSuitableNode();
    		String t1="";
    		System.out.print(t1);
    		if(cNode==null){
    			return false;
    		}
    		TreeNode realNode=new TreeNode();
    		realNode.key=key;
    		if(cNode.leftChild==null){
    			cNode.leftChild=realNode;
    			realNode.parent=cNode;
    			//--请注意,需要检查是否有左边的靠近这边的兄弟,有的话需要修改指针。
    			if(cNode.parent!=null){
    			
    				TreeNode leftAncle=cNode.leftBrother;
    				
    				if(leftAncle!=null){
    					leftAncle.rightChild.rightBrother=realNode;
    					realNode.leftBrother=leftAncle.rightChild;					
    				}
    				
    				
    			}
    			recursion_adjustment_after_insert(realNode);
    			
    			return true;
    		}
    		else if(cNode.rightChild==null){
    			cNode.rightChild=realNode;
    			realNode.parent=cNode;
    			cNode.leftChild.rightBrother=realNode;
    			realNode.leftBrother=cNode.leftChild;
    			recursion_adjustment_after_insert(realNode);
    			return true;
    		}
    		
    		
    		// TODO Auto-generated method stub
    		return false;
    	}
    	private TreeNode ___suitableNode=null;
    	
    	public boolean delete(float key){
    		TreeNode lastNode=getLastNode();
    		if(lastNode==null){
    			return false;
    		}
    		if(_rootNode==null){
    			return false;
    		}
    		TreeNode deletedNode=getNode(key);
    
    		if(deletedNode==null){
    			return false;
    		}
    		
    	
    		
    		TreeNode lastParent=lastNode.parent;
    		
    		
    		if(lastParent!=null){
    			boolean isLeft=true;
    			if(lastParent.rightChild!=null&&lastParent.rightChild.key==lastNode.key){
    				isLeft=false;
    			}
    			if(isLeft==true){
    				lastParent.leftChild=null;
    				if(lastParent.leftBrother!=null){
    					lastParent.leftBrother.rightChild.rightBrother=null;
    				}
    			}else{
    				lastParent.rightChild=null;
    				lastParent.leftChild.rightBrother=null;
    			}
    			/**
    			 * 注意,假如删除的节点没有左右子节点,并且它与最后的真实删除的节点并非同一个,那么就必须上浮调整各个节点的位置了。
    			 * */
    			if(deletedNode.leftChild==null&&deletedNode.rightChild==null&&deletedNode.key!=lastNode.key){
    				deletedNode.key=lastNode.key;
    		     	recursion_adjustment_after_insert(deletedNode);
    				return true;
    			}
    /**
     * 假如需要删除的节点跟最后节点是一样的,那么我们可以认为这个节点就是最后的节点。那么直接删除就好了。
     * */
    			else if(deletedNode.key==lastNode.key){
    				
    				return true;
    			}
    			else{
    				deletedNode.key=lastNode.key;
    				recursion_adjustment_after_deletion(deletedNode);
    				return true;
    			}
    		}
    		else{
    		_rootNode=new TreeNode();	
    		return true;
    		}
    		
    	}
    	
    	private TreeNode getSuitableNode(){
    		if(_rootNode==null){
    			return null;
    		}
    		if(_rootNode.leftChild==null){
    			return _rootNode;
    		}
    		
    		/**
    		 * 查看最左侧节点。
    		 * */
    		TreeNode preNode=null;
    		TreeNode cNode=_rootNode;
    		int theHeight=1;
    		while(cNode.leftChild!=null){
    			theHeight++;
    			cNode=cNode.leftChild;
    		}
    		int lvMaxNodes=(int)Math.pow(2.0, (double)(theHeight-1));
    		int lvRealNodes=1;
    		TreeNode lvLastNode=cNode;
    		while (lvLastNode.rightBrother!=null) {
    			lvRealNodes++;
    			lvLastNode=lvLastNode.rightBrother;
    			
    		}
    		
    		//判断当前节点所在层数的节点数量是否已经满了。
    		if(lvRealNodes<lvMaxNodes){
    			boolean isLeft=true;
    			TreeNode parentNode=lvLastNode.parent;
    			
    			if(parentNode.rightChild!=null&&parentNode.rightChild.key==lvLastNode.key){
    				isLeft=false;
    			}
    			else if(parentNode.leftChild!=null&&parentNode.leftChild.key==lvLastNode.key){
    				isLeft=true;
    			}
    			if(isLeft==true){
    				return parentNode;
    			}
    			else{
    				if(parentNode.rightBrother==null){
    					return cNode;
    				}
    				else{
    					return parentNode.rightBrother;
    				}
    			}
    		}
    		else{
    			
    			return cNode;
    		}
    				
    		
    		
    	}
    
    
    
    	public boolean pop() {
    		// TODO Auto-generated method stub
    		return false;
    	}
    
    	public boolean containsKey(float key) {
    		// TODO Auto-generated method stub
    		___containsKey=false;
    		recursion_search_key(_rootNode, key);
    		
    		return ___containsKey;
    	}
    	private boolean ___containsKey=false;
    	private void recursion_search_key(TreeNode node,float key){
    		if(node==null){
    			return;
    		}
    		if(node.key==key){
    			___containsKey=true;
    			return;
    		}
    		recursion_search_key(node.leftChild, key);
    		recursion_search_key(node.rightChild, key);
    	}
    	
    	private TreeNode ___searchNode=null;
    	public TreeNode getNode(float key){
    		___searchNode=null;
    		recursion_search_node(_rootNode, key);
    		return ___searchNode;
    	}
    	
    	private void recursion_search_node(TreeNode currentNode,float key){
    		if(currentNode==null){
    			return;
    		}
    		if(currentNode.key==key){
    			___searchNode=currentNode;
    			return;
    		}
    		else{
    			recursion_search_node(currentNode.leftChild, key);
    			recursion_search_node(currentNode.rightChild, key);
    		}
    	}
    	
    	/**
    	 * 请注意,simpleinsert这个方法只是单纯将关键字插入到二叉树里面,
    	 * 每次查完它都不会主动调整使其成为一个最小堆,为什么要有这个方法呢?
    	 * 因为每个需要排序的数组往往有多个数字,假如每次插入都调整那么就很麻烦了,
    	 * 倒不如插入以后,一次性调整。
    	 * 
    	 * */
    	private boolean simpleInsert(float key){
    		/**
    		 * 假如当前节点为null,那么可以判断是第一次插入关键字,直接插入。
    		 * */
    		if(_rootNode==null){
    			_rootNode=new TreeNode();
    			_rootNode.key=key;
    			_arrContainer.add(key);
    			return true;
    		}
    		/**
    		 * 假如当前为root根节点,并且没有子节点,那么就插入到根节点的左孩子
    		 * */
    		if(_rootNode!=null&&_rootNode.leftChild==null&&_rootNode.rightChild==null){
    			TreeNode cNode=new TreeNode();
    			cNode.key=key;
    			cNode.parent=_rootNode;
    			_rootNode.leftChild=cNode;
    			//recursion_adjustment_after_insert(cNode);
    			
    			return true;
    		}
    		/**
    		 * 假如当前为root节点,并且有左子节点,没有右子节点,那么直接添加右子节点。
    		 * */
    		if(_rootNode!=null&&_rootNode.leftChild!=null&&_rootNode.rightChild==null){
    			TreeNode cNode=new TreeNode();
    			cNode.key=key;
    			cNode.parent=_rootNode;
    			_rootNode.rightChild=cNode;
    			
    			_rootNode.leftChild.rightBrother=cNode;
    			cNode.leftBrother=_rootNode.leftChild;
    			//recursion_adjustment_after_insert(cNode);
    			
    			return true;
    		}
    		/**
    		 * 假如这些都不是,那么就判断该树形是不是已经满了,满了的话,直接在最左边添加一个左子节点,
    		 * 否则,找出最后的那一个叶子节点,然后判断并添加一个节点。
    		 * */
    		
    		TreeNode cNode=getSuitableNode();
    		String t1="";
    		System.out.print(t1);
    		if(cNode==null){
    			return false;
    		}
    		TreeNode realNode=new TreeNode();
    		realNode.key=key;
    		if(cNode.leftChild==null){
    			cNode.leftChild=realNode;
    			realNode.parent=cNode;
    			//--请注意,需要检查是否有左边的靠近这边的兄弟,有的话需要修改指针。
    			if(cNode.parent!=null){
    			
    				TreeNode leftAncle=cNode.leftBrother;
    				
    				if(leftAncle!=null){
    					leftAncle.rightChild.rightBrother=realNode;
    					realNode.leftBrother=leftAncle.rightChild;					
    				}
    				
    				
    			}
    			recursion_adjustment_after_insert(realNode);
    			
    			return true;
    		}
    		else if(cNode.rightChild==null){
    			cNode.rightChild=realNode;
    			realNode.parent=cNode;
    			cNode.leftChild.rightBrother=realNode;
    			realNode.leftBrother=cNode.leftChild;
    			//recursion_adjustment_after_insert(realNode);
    			return true;
    		}
    		
    		
    		// TODO Auto-generated method stub
    		return false;		
    	}
    	
    private void recursion_adjustment_after_insert(TreeNode _node){
    	if(_node==null){
    		return;
    	}
    	TreeNode parentNode=_node.parent;
    	if(parentNode==null){
    		return;
    	}
    	if(_node.key<parentNode.key){
    		float tmp1=parentNode.key;
    		parentNode.key=_node.key;
    		_node.key=tmp1;
    		recursion_adjustment_after_insert(parentNode);
    		return;
    		
    	}
    	else{
    		return;
    	}
    }
    
    private void recursion_adjustment_in_inition(TreeNode currentNode){
    	if(currentNode==null){
    		return;
    	}
    	if(currentNode.leftChild==null){
    		return;
    	}
    	TreeNode leftChild=currentNode.leftChild;
    	TreeNode rightChild=currentNode.rightChild;
    	float tmpKey=currentNode.key;
    	if(leftChild!=null&&rightChild!=null){
    		if(leftChild.key<currentNode.key&&rightChild.key<currentNode.key){
    			
    			if(leftChild.key<=rightChild.key){
    				currentNode.key=leftChild.key;
    				leftChild.key=tmpKey;
    				
    				recursion_adjustment_in_inition(leftChild);
    				return;
    			}
    			else{
    				currentNode.key=rightChild.key;
    				rightChild.key=tmpKey;
    				recursion_adjustment_in_inition(rightChild);
    				return;
    			}
    		}
    		else if(leftChild.key<currentNode.key&&rightChild.key>=currentNode.key){
    			currentNode.key=leftChild.key;
    			leftChild.key=tmpKey;
    			
    			recursion_adjustment_in_inition(leftChild);
    			return;
    		}
    		else if(leftChild.key>=currentNode.key&&rightChild.key<currentNode.key){
    			currentNode.key=rightChild.key;
    			rightChild.key=tmpKey;
    			recursion_adjustment_in_inition(rightChild);
    			return;
    		}
    		else{
    			return;
    		}
    	}
    	else if(leftChild!=null&&rightChild==null){
    		if(leftChild.key<currentNode.key){
    			currentNode.key=leftChild.key;
    			leftChild.key=tmpKey;
    			
    			recursion_adjustment_in_inition(leftChild);
    			return;
    		}		
    		else{
    			return;
    		}
    	}
    	else{
    		return;
    	}
    }
    
    /**
     * 当前节点被删除后,下沉过程调整。
     * */
    private void recursion_adjustment_after_deletion(TreeNode currentNode){
    	if(currentNode==null){
    		return;
    	}
    	float ftmp=currentNode.key;
    	if(currentNode.leftChild==null&¤tNode.rightChild==null){
    		return;
    	}
    	if(currentNode.leftChild!=null&¤tNode.rightChild!=null){
    		if(currentNode.leftChild.key<currentNode.key&¤tNode.rightChild.key<currentNode.key){
    			if(currentNode.leftChild.key<=currentNode.rightChild.key){
    				currentNode.key=currentNode.leftChild.key;
    				currentNode.leftChild.key=ftmp;
    				
    				recursion_adjustment_after_deletion(currentNode.leftChild);
    				return;
    			}
    			else{
    				currentNode.key=currentNode.rightChild.key;
    				currentNode.rightChild.key=ftmp;
    				recursion_adjustment_after_deletion(currentNode.rightChild);
    				return;
    				
    			}
    		}
    		else if(currentNode.leftChild.key<currentNode.key){
    			currentNode.key=currentNode.leftChild.key;
    			currentNode.leftChild.key=ftmp;
    			recursion_adjustment_after_deletion(currentNode.leftChild);
    			return;
    			
    		}
    		else if(currentNode.rightChild.key<currentNode.key){
    			currentNode.key=currentNode.rightChild.key;
    			currentNode.rightChild.key=ftmp;
    			recursion_adjustment_after_deletion(currentNode.rightChild);
    			return;
    		}
    		else{
    			return;
    		}
    	}
    	else if(currentNode.leftChild!=null&¤tNode.rightChild==null){
    		 if(currentNode.leftChild.key<currentNode.key){
    				currentNode.key=currentNode.leftChild.key;
    				currentNode.leftChild.key=ftmp;
    				recursion_adjustment_after_deletion(currentNode.leftChild);
    				return;
    				
    			}
    		 return;
    	}
    	else{
    		return;
    	}
    	
    }
    
    private TreeNode getLastNode(){
    	if(_rootNode==null){
    		return null;
    	}
    	TreeNode cNode=_rootNode;
    	while(cNode.leftChild!=null){
    		cNode=cNode.leftChild;
    	}
    	TreeNode lvLastNode=cNode;
    	while(lvLastNode.rightBrother!=null){
    		lvLastNode=lvLastNode.rightBrother;
    	}
    	return lvLastNode;
    }
    /**
     * 根据index来获得节点,请注意,index从零开始。
     * */
    public TreeNode getTreeNodeByIndex(int loc){
    	if(_rootNode==null){
    		return null;
    	}
    	if(loc<=-1){
    		return null;
    	}
    	int cindex=0;
    	if(loc==0){
    		return _rootNode;
    	}else{
    		int theHeight=1;
    		TreeNode leftNode=_rootNode;
    		
    		while(leftNode.leftChild!=null){
    			leftNode=leftNode.leftChild;
    			theHeight++;
    		}
    		int cHeight=1;
    		TreeNode resultNode=null;
    		TreeNode lvFirstNode=_rootNode;
    		
    		TreeNode tmpRightNode=null;
    		
    		
    		for(cindex=0;cindex<=loc;cindex++){
    			if(cHeight>theHeight){
    				break;
    			}
    		    if(lvFirstNode==null){
    		    	break;
    		    }	
    		    
    		    
    		    if(loc==0){
    		    	return _rootNode;
    		    }
    		    
    		    tmpRightNode=lvFirstNode;
    		    
    		    while(tmpRightNode!=null){
    		    	if(cindex==loc){
    		    		return tmpRightNode;
    		    	}
    		    	tmpRightNode=tmpRightNode.rightBrother;
    		    	if(tmpRightNode==null){
    		    		break;
    		    	}
    		    	else{
    		    		cindex++;	
    		    	}
    		    	
    		    }
    			
    			
    			
    			lvFirstNode=lvFirstNode.leftChild;
    	        cHeight++;
    		}
    		
    		return resultNode;
    	}
    	
    }
    public void fromArray_origin(float[] arr){
    	_rootNode=null;
    	if(arr==null){
    		return;
    	}
    	else{
    		for(float f1:arr){
    			simpleInsert(f1);
    		}
    	}
    	int theLength=arr.length;
    	int middle_loc=(int)Math.floor((double)((double)theLength/2.0))-1;
    	if(theLength<=1){
    		return ;
    	}
    	//--循环进行上浮调整。
    }
    /**
     * 将原始数组构建成为完全二叉树,再调整成为最小堆,然后
     * 返回堆的根节点。
     * 请注意查看我摘抄的图文教程,主要就是从最后一个不为叶子节点的节点开始,
     * 通过比较进行下沉,直到根节点结束。
     * 当然,假如您的节点数据里面没有leftBrother之类的指针你会发现按照排位寻找节点是如此麻烦。
     * */
    
    public TreeNode fromArray(float[] arr){
    	_rootNode=null;
    	if(arr==null){
    		return null;
    	}
    	else{
    		for(float f1:arr){
    			simpleInsert(f1);
    		}
    	}
    	int theLength=arr.length;
    	int middle_loc=(int)Math.floor((double)((double)theLength/2.0))-1;
    	System.out.println("最下面的非叶子节点:【"+middle_loc+"】");
    	if(theLength<=1){
    		return _rootNode;
    	}
    	//--循环进行上浮调整。
    	for(int i=middle_loc;i>=0;i--){
    		TreeNode cNode=getTreeNodeByIndex(i);
    		recursion_adjustment_in_inition(cNode);
    		
    	}
    	
    	return _rootNode;
    }
    /**
     * 通过根节点来逐个读取数字,然后组成从小到大的数组。
     * */
    public ArrayList<Float> toArray(){
    	
    	
    	
    	
    	if(_rootNode==null){
    		return null;
    	}
    	
    	ArrayList<Float> _arr=new ArrayList<Float>();
    	while(_rootNode!=null){
    		_arr.add(_rootNode.key);
    		deleteNode(_rootNode);
    	}
    	
    
    	
    	
    	return _arr;
    }
    
    
    public boolean deleteNode(TreeNode currentNode){
    	TreeNode lastNode=getLastNode();
    
    	TreeNode deletedNode=currentNode;
    
    	if(deletedNode==null){
    		return false;
    	}
    	
    	/**
    	 * 假如只有一个根节点,没有子节点的话,那么就直接删除
    	 * */
     if(currentNode!=null&¤tNode.parent==null&¤tNode.leftChild==null&¤tNode.rightChild==null){
    	 _rootNode=null;
    	 currentNode=null;
    	 return true;
     }	
    	
    
    	
    	TreeNode lastParent=lastNode.parent;
    	
    	
    	if(lastParent!=null){
    		boolean isLeft=true;
    		if(lastParent.rightChild!=null&&lastParent.rightChild.key==lastNode.key){
    			isLeft=false;
    		}
    		if(isLeft==true){
    			lastParent.leftChild=null;
    			if(lastParent.leftBrother!=null){
    				lastParent.leftBrother.rightChild.rightBrother=null;
    			}
    		}else{
    			lastParent.rightChild=null;
    			lastParent.leftChild.rightBrother=null;
    		}
    		/**
    		 * 注意,假如删除的节点没有左右子节点,并且它与最后的真实删除的节点并非同一个,那么就必须上浮调整各个节点的位置了。
    		 * */
    		if(deletedNode.leftChild==null&&deletedNode.rightChild==null&&deletedNode.key!=lastNode.key){
    			deletedNode.key=lastNode.key;
    	     	recursion_adjustment_after_insert(deletedNode);
    			return true;
    		}
    /**
    * 假如需要删除的节点跟最后节点是一样的,那么我们可以认为这个节点就是最后的节点。那么直接删除就好了。
    * */
    		else if(deletedNode.key==lastNode.key){
    			
    			return true;
    		}
    		else{
    			deletedNode.key=lastNode.key;
    			recursion_adjustment_after_deletion(deletedNode);
    			return true;
    		}
    	}
    	else{
    	_rootNode=new TreeNode();	
    	return true;
    	}
    	
    }
    
    
    }
    


    演示程序

    展开全文
  • 最小堆:是指根节点的关键字值是堆中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字值。 以下的操作以最大堆为例,最小堆相似。 最大堆的插入操作 步骤: 1、把当前节点数i设置...

    定义:

        最大堆和最小堆都是一棵完全二叉树。

        最大堆:是指根节点的关键字值是堆中的最大关键字值,且每个节点若有儿子节点,其关键字值都不小于其儿子节点的关键字值。

        最小堆:是指根节点的关键字值是堆中的最小关键字值,且每个节点若有儿子节点,其关键字值都不大于其儿子节点的关键字值。

        以下的操作以最大堆为例,最小堆相似。


    最大堆的插入操作

       步骤:

    1. 把待增加的节点编号 i 设置为已知堆的总节点数加 1 即 i=++(*n),因此,新增的元素放在最下一层作为新的叶子节点。求出节点 i 的父节点 parent=i/2; 判断是否为空堆,并比较所插入元素与父节点关键字值的大小;
    2. 若所插入节点关键字值大于父节点关键字值即item>heap[parent],则把父节点向下移,并把父节点作为当前节点,依次求父节点,即依次沿着树枝向上延伸直到根节点;
    3. 把元素item插入到正确位置;

    最大堆的删除操作

        最大堆的删除,即删除最大的元素。我们先取最后的元素提到根结点,然后删除最大值,然后再把新的根节点放到合适的位置。

       首先删除根节点,并把最后一个节点临时作为新的根节点,将新的根节点作为当前节点与其孩子节点中最大的关键值节点进行比较,若小于其孩子节点的关键值,则与其孩子节点进行交换位置,并把新位置作为当前节点继续与其孩子节点进行比较,一直延伸下去,直到没有孩子节点为止;

    源程序

        函数声明:

    #ifndef HEAP_H_INCLUDED
    #define HEAP_H_INCLUDED
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX_SIZE 10
    int heap[MAX_SIZE];
    void max_Heap_insert(int *heap,int *n,int item);
    int max_Heap_delete(int *heap,int *n);
    #endif // HEAP_H_INCLUDED
    
       函数的定义:

    #include"heap.h"
    
    /*最大堆的插入操作*/
    /*注:堆的下标是从1开始,而不是0*/
    void max_Heap_insert(int *heap,int *n,int item)
    {
        int i,parent;//i为当前节点,parent为i的父节点
        if((*n)==MAX_SIZE)//堆为满
        {
            printf("The heap is full\n");
            exit(1);
        }
        i=++(*n);
        parent=i/2;
        while((i!=1) && (item>heap[parent]))//若堆为非空,且所插入数据item大于父节点的关键字值
        {
            heap[i]=heap[parent];//父节点关键字值下移
            i=parent;//把父节点作为当前节点
            parent/=2;//依次求父节点
        }
        heap[i]=item;//插入到正确的位置
    }
    /*最大堆的删除操作*/
    int max_Heap_delete(int *heap,int *n)
    {
        int item,temp;
        int child,parent;
        if(*n==0)//若为空堆
        {
            printf("The heap is empty.\n");
            exit(1);
        }
        item=heap[1];//把最大堆的最大元素赋给item
        temp=heap[(*n)--];//堆的最后节点关键字值
        parent=1;
        child=2*parent;
        while(child<=(*n))
        {
            if(child<*n && heap[child]<heap[child+1])
                child++;//找出堆中最大关键字值的节点
            if(temp>=heap[child])break;//把最大节点关键字值与最后节点关键字值比较
            else
            {//若堆中存在比最后节点关键字值大的节点,则交换位置
                heap[parent]=heap[child];
                parent=child;
                child*=2;
            }
        }
        heap[parent]=temp;//插入到正确位置
        return item;//返回删除的关键字值
    }
    
        程序测试:

    #include"heap.h"
    
    
    int main()
    {
        int item,i;
        int n=0;
        for(i=1;i<MAX_SIZE;i++)
        {
            scanf("%d",&item);
            max_Heap_insert(heap,&n,item);
        }
        for(i=1;i<=n;i++)
            printf("%d ",heap[i]);
        printf("\n");
        item=max_Heap_delete(heap,&n);
        printf("The deleted data is:%d",item);
        printf("\n");
        for(i=1;i<=n;i++)
            printf("%d ",heap[i]);
        return 0;
    }

    展开全文
  • 最小堆实现最小优先队列

    千次阅读 2018-09-12 12:48:20
    最小优先队列的可以实现的操作: insert,插入一个元素 min,找到最小的元素 ...实现他的操作是依赖于的操作,比如要插入一个key,实际上就是在中去找key的位置,然后维护。所以要时刻清醒的是现在...
  • 最小堆实现最小优先级队列: //返回堆中关键字最小的元素 HeapMinimum() //去掉并返回堆中关键字最小的元素 HeapExtractMin() //将堆中元素x的关键字减小到k,k要小于x原来的关键字值 HeapDecreaseKey() //...
  • 的向上向下调整算法

    千次阅读 2019-06-06 01:24:22
    1、已知关键字序列5,8,12,19,28,20,15,22是最小堆插入关键字3,求调整后得到的最小堆 建堆: 插入关键字3: 从3开始向上调整,让它满足最小堆的特点,过程如下: 3和19交换位置 3和8交换位置: 3和5交换位置 ...
  • 插入法建

    千次阅读 2012-09-26 11:31:41
    插入一个关键字就与其父节点的关键字比较大小,如果父节点的关键字较小则交换,然后依次自低地向上调整使之符合大(小)顶堆的特性。 插入法建与调整法建可能结果不一样。调整法建是自底向上依次调整,一棵...
  • 的创建,插入,删除,建立

    千次阅读 2018-10-23 11:18:49
    什么是堆 优先队列( (Priority Queue ):特殊的“ 队列” ,取出元素的顺序是依照元素的 优先权(关键字)。 大小,而不是元素进入队列的先后顺序。 优先队列的完全二叉树示 ...“最小堆( MinHeap) ...
  • 插入一个关键字就与其父节点的关键字比较大小,如果父节点的关键字较小则交换,然后依次自低地向上调整使之符合大(小)顶堆的特性。 插入法建与调整法建可能结果不一样。调整法建是自底向上依次调整,一棵...
  • 首先定义优先队列,优先队列是一种特殊的队列,取出元素的顺序是依据优先权...反之称为最小堆。 堆结构常进行的操作有(以最大堆为例子): 一 定义堆的结构: typedef struct HeapStruct *MaxHeap; str...
  • 选择,插入,希尔,归并,快排(包括三向快排),排序。  选择:  实现原理:内外循环,选择最小,比较。  关键点:for(k =i+1 ,k<N,k++){a[j]<a[min],min=j}  插入:  实现原理:往左插入最小 ...
  • http://jingyixiao.com/?p=823,该说排序了的定义:n个关键字序列Kl,K2,…,Kn称为,当且仅当该序列满足如下性质(简称为性质...的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素。排序算法
  • 2018-05-29 14:57:45
    若采用数组或链表实现优先队列数组:插入——元素总是插入尾部 删除——查找最大(或最小关键字。从数组中删去需要移动元素 O(n)链表:插入——元素总是插入链表的头部删除——查找最大(或最小关键字,删去...
  • 文章目录单选题选择题题解编程题...已知关键字序列(5,8,12,19,28,20,15,22)是最小堆(小根堆),插入关键字3,调整后得到的最小堆是: 3,5,12,8,28,20,15,22,19 4 哪种树,树中任何结点到根结点路
  • 常用排序之排序法

    千次阅读 2017-09-07 10:32:57
    实际上是一棵完全二叉树,分为大顶堆和小顶堆,大顶堆的顶的关键字是最大的,小顶堆的顶的关键字最小的。排序思想:利用大顶堆(小顶堆)顶记录的是最大关键字(最小关键字)这一特性。一般用数组来表示...
  • 最大学习笔记

    2020-09-21 09:39:45
    数据结构——最大学习目标:学习内容:最大的操作(创建、插入、删除) 学习目标: 最大 学习内容: 优先队列:特殊的“队列”,取出元素的顺序是依照元素的优先权(关键字)大小,而不是元素进入队列的顺序...
  • 排序

    2019-08-04 17:24:05
    如果是最小值,称为最小堆。 基于第一个特性,可以用一个一维数组去存这个堆,起始下标为1。 对于堆的操作,下面只给出最大堆的插入和删除的操作。 插入元素 如图所示: 其主要思想是: 先将元素放入数组的最后...
  • 数据结构---

    2020-03-24 22:00:31
    二、区分最大堆和最小堆 三、堆的抽象数据类型描述 这里举例用最大堆,最小堆同理 四、最大堆的建立 五、最大堆的插入 六、最大堆的删除 七、最大堆的打印 一、堆的两个特性 结构性:用...
  • 斐波那契的C#实现

    2020-04-24 15:49:29
    斐波那契的C#实现,包括插入操作,抽取最小结点操作和关键字减值操作,示例数据使用算法导论第三版中的数据
  • 计算机专业基础综合数据结构排序...已知关键字序列58121928201522是小根堆(最小堆)插入关键字3调整后得到的小根堆是( )2009年全国试题9(2分) 分数2.00 A.351282820152219 B.351219201 522828 C.381252015222819 D.3125
  • 二项

    2013-12-17 12:48:05
    二项[编辑] 在计算机科学中,二项(binomial heap)是一种类似于二叉结构。与二叉相比,其优势是可以快速合并两个,因此它...3.1 合并3.2 插入3.3 查找最小关键字所在结点3.4 删除最小关键字所在
  • 斐波那契的C#实现,包括插入操作,抽取最小结点操作和关键字减值操作,示例数据使用算法导论第三版中的数据
  • 可合并是支持以下5种操作的数据结构,其中... INSERT(H, x):将一个已填入关键字的元素x插入堆H中。 MINIMUM(H):返回一个指向H中具有最小关键字元素的指针。 EXTRACT-MIN(H):从H中删除最小关键字的元素...
  • 请不懂的读者去查资料),排序分为两种,大顶堆和小顶堆,大顶堆的意思就是顶元素是整个中最大的,小顶堆的意思就是顶元素是整个最小的,满足:任何一非叶节点的关键字不大于或者不小于其左右孩子节点...
  • 3.树之、哈夫曼树以及集合

    千次阅读 2019-04-14 10:07:15
    的定义 优先队列(priority queue):特殊的“队列”,却出元素的顺序是依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序。 若采用数组或者链表实现优先队列: 数组 插入:元素总是插入尾部...
  • 二叉部分练习

    2017-04-01 20:42:00
    本练习主要做了几个工作: 1.给定一个数组来初始化二叉,第一种方法是通过不断插入,时间复杂度是O(nlgn),第二种方法是先...二叉的下滤和上滤,对二叉堆关键字的操作诸如删除最小,增加某关键字值,减少某关...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 166
精华内容 66
关键字:

最小堆插入关键字