<commit_before>\section{\module{heapq} ---
         Heap queue algorithm}

\declaremodule{standard}{heapq}
\modulesynopsis{Heap queue algorithm (a.k.a. priority queue).}
\moduleauthor{<NAME>}{}
\sectionauthor{<NAME>}{<EMAIL>}
% Theoretical explanation:
\sectionauthor{Fran\c <NAME>}{}
\versionadded{2.3}


This module provides an implementation of the heap queue algorithm,
also known as the priority queue algorithm.

Heaps are arrays for which
\code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+1]} and
\code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+2]}
for all \var{k}, counting elements from zero.  For the sake of
comparison, non-existing elements are considered to be infinite.  The
interesting property of a heap is that \code{\var{heap}[0]} is always
its smallest element.

The API below differs from textbook heap algorithms in two aspects:
(a) We use zero-based indexing.  This makes the relationship between the
index for a node and the indexes for its children slightly less
obvious, but is more suitable since Python uses zero-based indexing.
(b) Our pop method returns the smallest item, not the largest (called a
"min heap" in textbooks; a "max heap" is more common in texts because
of its suitability for in-place sorting).

These two make it possible to view the heap as a regular Python list
without surprises: \code{\var{heap}[0]} is the smallest item, and
\code{\var{heap}.sort()} maintains the heap invariant!

To create a heap, use a list initialized to \code{[]}, or you can
transform a populated list into a heap via function \function{heapify()}.

The following functions are provided:

\begin{funcdesc}{heappush}{heap, item}
Push the value \var{item} onto the \var{heap}, maintaining the
heap invariant.
\end{funcdesc}

\begin{funcdesc}{heappop}{heap}
Pop and return the smallest item from the \var{heap}, maintaining the
heap invariant.
\end{funcdesc}

\begin{funcdesc}{heapify}{x}
Transform list \var{x} into a heap, in-place, in linear time.
\end{funcdesc}

\begin{funcdesc}{heapreplace}{heap, item}
Pop and return the smallest item from the \var{heap}, and also push
the new \var{item}.  The heap size doesn't change.<commit_msg>Document that heappop() and heapreplace() raise IndexError if the heap is empty.<commit_after>\section{\module{heapq} ---
         Heap queue algorithm}

\declaremodule{standard}{heapq}
\modulesynopsis{Heap queue algorithm (a.k.a. priority queue).}
\moduleauthor{<NAME>}{}
\sectionauthor{<NAME>}{<EMAIL>}
% Theoretical explanation:
\sectionauthor{Fran\c <NAME>}{}
\versionadded{2.3}


This module provides an implementation of the heap queue algorithm,
also known as the priority queue algorithm.

Heaps are arrays for which
\code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+1]} and
\code{\var{heap}[\var{k}] <= \var{heap}[2*\var{k}+2]}
for all \var{k}, counting elements from zero.  For the sake of
comparison, non-existing elements are considered to be infinite.  The
interesting property of a heap is that \code{\var{heap}[0]} is always
its smallest element.

The API below differs from textbook heap algorithms in two aspects:
(a) We use zero-based indexing.  This makes the relationship between the
index for a node and the indexes for its children slightly less
obvious, but is more suitable since Python uses zero-based indexing.
(b) Our pop method returns the smallest item, not the largest (called a
"min heap" in textbooks; a "max heap" is more common in texts because
of its suitability for in-place sorting).

These two make it possible to view the heap as a regular Python list
without surprises: \code{\var{heap}[0]} is the smallest item, and
\code{\var{heap}.sort()} maintains the heap invariant!

To create a heap, use a list initialized to \code{[]}, or you can
transform a populated list into a heap via function \function{heapify()}.

The following functions are provided:

\begin{funcdesc}{heappush}{heap, item}
Push the value \var{item} onto the \var{heap}, maintaining the
heap invariant.
\end{funcdesc}

\begin{funcdesc}{heappop}{heap}
Pop and return the smallest item from the \var{heap}, maintaining the
heap invariant.  If the heap is empty, \exception{IndexError} is raised.
\end{funcdesc}

\begin{funcdesc}{heapify}{x}
Transform list \var{x} into a heap, in-place, in linear time.
\end{funcdesc}

\begin{funcdesc}{heapreplace}{heap, item}
Pop and return the smallest item from the \var{heap}, and also push
the new \var{item}.  The heap size doesn't change.
If the heap is empty, \exception{IndexError} is raised.
{'fraction_non_alphanumeric': 0.11172812083518437, 'fraction_numerical': 0.003553976010661928, 'mean_word_length': 4.848051948051948, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1506885', 'n_tokens_mistral': 1335, 'n_tokens_neox': 1310, 'n_words': 570}