.. _Heaps:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Heaps";ODSA.SETTINGS.MODULE_LONG_NAME = "Heaps and Priority Queues";ODSA.SETTINGS.MODULE_CHAPTER = "Week 5"; ODSA.SETTINGS.BUILD_DATE = "2016-11-29 20:59:56"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer


=====
Heaps
=====

Heaps
-----

Complete Trees
~~~~~~~~~~~~~~   
   .. odsalink:: AV/slides.css
   .. odsalink:: AV/Binary/heapbuildProofCON.css
  
   .. _BinArray:

   .. figure:: Images/BinArray.png
      :width: 300
      :align: center
      :alt: Complete binary tree node numbering

   .. math::

      \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
      \hline
      \textrm{Position} & 0  & 1 & 2 & 3 &  4 &  5 & 6 & 7 & 8 &  9 & 10 & 11\\
      \hline
      \hline
      \textrm{Parent} & \,--\, & 0 & 0 & 1 &  1 &  2 &  2 & 3 & 3 & 4 & 4 & 5\\
      \hline
      \textrm{Left Child} & 1  & 3 & 5 & 7 &  9 & 11 & \,--\, & \,--\, & \,--\, &
      \,--\, & \,--\, &  \,--\,\\
      \hline
      \textrm{Right Child} & 2  & 4 & 6 & 8 & 10 & \,--\, & \,--\, & \,--\, &
      \,--\, & \,--\, & \,--\, &  \,--\,\\
      \hline
      \textrm{Left Sibling} & \,--\, & \,--\, & 1 & \,--\, &  3 & \,--\, & 5 &
      \,--\, & 7 & \,--\, &  9 &  \,--\,\\
      \hline
      \textrm{Right Sibling} & \,--\, & 2 & \,--\, & 4 & \,--\, &  6 & \,--\, & 8 &
      \,--\, & 10 & \,--\, & \,--\,\\
      \hline
      \end{array}


Heap insert
~~~~~~~~~~~
   .. inlineav:: heapinsertCON ss
      :long_name: Heap insert Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: DataStructures/binaryheap.js
   .. odsascript:: AV/Binary/heapinsertCON.js


Building a Heap
~~~~~~~~~~~~~~~
   .. inlineav:: heapbuildCON ss
      :long_name: Heapbuild Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/heapbuildCON.js


Building a Heap Proof
~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: heapbuildProofCON ss
      :long_name: Heap build analysis proof Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/heapbuildProofCON.js


Delete the maximum value
~~~~~~~~~~~~~~~~~~~~~~~~
   .. inlineav:: heapmaxCON ss
      :long_name: Remove Max Slideshow
      :points: 0.0
      :required: False
      :threshold: 1.0
      :output: show

   .. odsascript:: AV/Binary/heapmaxCON.js